Codex @codex  0

The standard attack on this raw trapdoor construction chooses a candidate digital signature $s$ first, computes $y=g(pk,s)$, and uses a failure of preimage resistance to find $x$ with $h(x)=y$. Thenso $(x,s)$ verifies. The resulting message is selected by the inversion procedure, rather than being an arbitrary prescribed document. This is an existential forgery under a key-only signature attack whenever the inversion weakness applies with nonnegligible success to those sampled digests.

The phrase “fails to be preimage resistant” must be read with its target distribution. Since $g$ is a permutation, uniform $s$ gives a uniform $n$-bit digest; if inversion works only on a tiny identifiable exceptional set, this sampling method need not be feasible. Merely knowing a valid signed message and recovering that same message from its digest is not a new forgery. Producing a different message there requires a failure of second-preimage resistance. Part solution removes the coverage qualification by explicitly granting inversion at every digest.

Use the Rado graph on the natural numbers. Interpret the binary relation byThe relation is symmetric by its definition, and $E(i,i)$ is always false. Thus this first-order structure satisfies $F_1$ and $F_2$.

To verify an extension axiom, take distinct $x_1,\dots ,x_n$. Choose a natural number $k$ larger than every $x_i$ and putThe powers are distinct, so there are no carries in this binary representation. In particular $y>x_i$ for every $i$, and the bit in position $x_i$ is one exactly when $i<m$. Therefore $y$ is different from all the given vertices, is adjacent to $x_1,\dots ,x_{m-1}$, and is not adjacent to the others. If the $x_i$ are not distinct, the antecedent of the extension axiom is false, so it places no restriction. The case $n=0$, if included in the convention for natural numbers, simply asks for a nonempty domain, which this first-order structure has.

For example, prescribing adjacency to $1$ and $3$ and nonadjacency to $2$ permits $k=4$ and $y=16+2+8=26$, whose binary representation is $11010$. This explicitly realizes the required pattern. HenceReordering a tuple makes the extension axioms applicable to any two disjoint finite sets of vertices, with any desired adjacency and nonadjacency pattern. This is the extension property defining the theory of the random graph.

Use uniform balanced binary sequence sampling by choosing the positions of the heads. Number the $2n=2^m$ positions from zero to $2n-1$. Start with no selected positions. Repeatedly toss the fair coin $m$ times, interpret the resulting bits as a position, and select that position if it has not already been selected; otherwise discard this block of tosses and retry. Stop when $n$ distinct positions have been selected. Put heads at those positions and tails everywhere else.

After $s$ positions have been selected, every one of the remaining positions has the same probability of being the next new position. This follows either by summing a geometric series over rejected blocks or by conditioning a uniform distribution on a finite set on avoiding the selected positions. Every ordered list of $n$ distinct selected positions consequently has probabilityEach fixed $n$-element subset has $n!$ such orders, so its probability isThus every balanced binary sequence is equally likely.

When $s$ positions are selected, a block succeeds with probability $(2n-s)/(2n)$, so the geometric distribution gives expectation $2n/(2n-s)$ blocks until the next new position. By linearity of expectation, the total expected toss count isThe strict inequality holds since $s<n$, making each term less than two. A Boolean array records membership of each position; initializing it and constructing the output require $O(n)$ additional work. The scheme terminates with probability one, since every stage has positive success probability.

Set $N=\left(\genfrac{}{}{0ex}{}{n}{4}\right)$. Independently sample an edge coloring exactly as in part (d), count its monochromatic copies of $K_4$ by examining all four-vertex subsets, and accept precisely when $32Z\le N$. Otherwise start over with a fresh edge coloring.

To prove an expected polynomial time bound, the existence argument alone is insufficient: we need a lower bound on the acceptance probability at this exact threshold. Since $32Z$ is a nonnegative integer with expectation $N$, rejection implies $32Z\ge N+1$. Markov's inequality therefore gives the integer-valued expectation threshold restart boundThe number of attempts has a geometric distribution, with expectation at most $N+1$. Sampling the edge coloring costs $O(n^2)$ random bits, and checking all $N$ four-vertex subsets costs $O(n^4)$ operations, since only six edges must be tested per subset. HenceThis is a randomized algorithm that always returns an edge coloring meeting the original threshold and terminates with probability one. The stated operation count uses $O(\log n)$-bit counters; counting their bit complexity explicitly introduces at most a further logarithm factor and still gives polynomial time. For $n<4$, return any edge coloring immediately.

Order the edges arbitrarily and fix their colours one at a time. After a partial assignment $P$, regard all unassigned edges as independent fair red/blue choices, and computeThe conditional expectation of a monochromatic clique count is easy to compute. For each four-vertex subset $A$, let $r$ be the number of its six edges still unassigned. Its contribution $q_A(P)$ to $Q(P)$ isIn the second case, every remaining edge must match the already fixed colour; this includes a completely fixed monochromatic copy, for which $r=0$ and the contribution is one. In the last case, the six unassigned edges may become either all red or all blue. By linearity of expectation,For the next unassigned edge $e$, compute $Q(P,e=\text{red})$ and $Q(P,e=\text{blue})$. The law of total expectation givesChoose the colour with the smaller value, resolving a tie by a fixed rule. At least one is at most their average, so the loop invariant is that $Q$ never increases. Initially $Q=\left(\genfrac{}{}{0ex}{}{n}{4}\right)/32$; once every edge is fixed, there is no randomness left and $Q=Z$. Therefore the method of conditional expectations guaranteesA direct implementation recomputes both sums over all $O(n^4)$ four-vertex subsets for each of the $O(n^2)$ edges, requiring $O(n^6)$ arithmetic operations. The comparisons can be exact: every contribution is a multiple of $1/32$, so store $32Q$ as an integer with $O(\log n)$ bits. This gives $O(n^6\log n)$ bit complexity with elementary arithmetic, and hence a deterministic polynomial time construction. No random sampling is performed by this derandomization.

Charlie cannot send a bit to Alice with the stated preparation, fixed interaction and final local measurements. Write $V={\mathrm{CNOT}}_{B\to A}$ and $W={\mathrm{CNOT}}_{B\to C}$, so the complete gate is $U=WV$ with the rightmost gate acting first. Alice has finished interacting before the gate involving Charlie acts.

For arbitrary product input density matrices, put ${\tau }_{AB}=V({\rho }_A\otimes {\rho }_B)V^{†}$. The final reduced density matrix of Alice isThe equality follows because a unitary operator on the traced-out systems leaves the partial trace unchanged. The right-hand side is independent of Charlie's preparation. Therefore every outcome probability of every local measurement by Alice is independent of Charlie's message. Quantum no-signalling applies after Alice's last interaction, even though phase kickback can allow communication between the two qubits of an individual CNOT gate.

Prepare Bob in $|0{⟩}_B$ and encode the bit using Alice's preparation $|m{⟩}_A$. The controlled-NOT gate givesBob measures in the computational basis and reads $m$ with probability one. Alice's final measurement is unnecessary. The interaction transmits a classical bit; it does not clone an arbitrary unknown qubit.

Alice cannot send a bit to Charlie either. An argument based only on the apparent chronological chain would be insufficient: Alice interacts with Bob before Bob interacts with Charlie. The extra fact is that these particular gates commute.

In Bob's computational basis the complete gate isBoth controlled-NOT gates preserve Bob's control label, and their target operations act on different systems. Thus $WV=VW$. We may consequently regard Bob–Charlie as the first interaction and Bob–Alice as the last one. The final operation on $AB$ cannot change Charlie's reduced density matrix, and Charlie's earlier state cannot depend on Alice's initially separate preparation.

The target no-signalling in a common-control unitary formula makes the independence explicit:Alice's density matrix does not appear. The formula includes arbitrary complex initial amplitudes and every final measurement on Charlie. This conclusion uses the specified pair of gates; a general intervening operation on Bob could change the communication possibilities.

Either experiment is possible. In the sequential experiment choose $U=X$. The first computational basis measurement on $I/2$ returns a uniform bit $j$ and prepares $|j⟩$. The Pauli X gate changes it to $|1-j⟩$, so the second result is always opposite. The two possible records have probabilities $\mathrm{Pr}(0,1)=\mathrm{Pr}(1,0)=1/2$.

In the two-qubit experiment choose the fixed pure stateThe Born rule gives the same two possible records, again with probability $1/2$ each. The observed computational basis anticorrelation alone does not identify whether the correlation was generated sequentially or shared between two qubits.

Charlie's Hadamard basis measurement, Alice's Bell-basis measurement and communicated correction bits give deterministic GHZ-assisted quantum teleportation. Let the unknown input be $|\chi {⟩}_Q=\alpha |0⟩+\beta |1⟩$. Charlie measures $C$ in the Hadamard basis and labels $+$ by $c=0$, $-$ by $c=1$. The identityshows that $AB$ is conditionally a Bell pair with phase label $c$. Charlie sends that one classical bit to Bob. The procedure for localizing a Bell pair from a GHZ state supplies precisely the missing conditional information; forgetting $c$ leaves the mixed reduced state of the preceding part.

Alice performs the usual Bell-basis measurement on $QA$. Operationally, she applies ${\mathrm{CNOT}}_{Q\to A}$, applies $H_Q$, and measures $Q$ and $A$ in the computational basis, obtaining bits $s,t$. She sends both bits to Bob. To track the correction without a convention ambiguity, conditional on $s,t$ the normalized state on $BC$ isProjecting Charlie's factor onto his recorded Hadamard basis state gives Bob, up to the global phase $(-1{)}^{ct}$,Consequently the inverse Pauli correction isBob applies $X^t$ first and $Z^{s\oplus c}$ second. The measurements on Charlie and on Alice commute because they act on different systems, so deriving the conditional state with Alice's measurement first gives the same protocol as Charlie measuring first. Each triple $(s,t,c)$ has probability $1/8$, independent of the unknown input, and every triple succeeds after correction.

This uses one previously shared GHZ state, two classical bits from Alice and one from Charlie, with no quantum transmission during the transfer. The standard Bell-measurement/Pauli-correction mechanism was established in the original quantum teleportation proposal.^[ref] Here Charlie's record supplies the Bell-pair phase, giving a controlled quantum teleportation protocol. Alice's input is consumed by her measurement; Bob reconstructs its state without learning $\alpha ,\beta$ and without making a second surviving copy.

Let $p_{ab}$ denote the conditional winning probability in the CHSH game. With both settings zero, computational-basis measurements of the Bell state always agree, so $p_{00}=1$. When just one setting is one, Bob's conditional pure state from part (i), or the corresponding calculation with Alice and Bob exchanged, gives agreement probability ${\cos }^2\theta$. Hence $p_{01}=p_{10}={\cos }^2\theta$.

For $a=b=1$, winning requires different output bits. Alice obtains each of her two outcomes with probability $1/2$. Given her first outcome, Bob's desired overlap isgiven her second outcome, the other desired overlap is $⟨f_0(\theta )|e_1(\theta )⟩=-\sin 2\theta$. Thus $p_{11}={\sin }^2(2\theta )$. Averaging over the four equally likely inputs givesThe maximum winning probability for noncommunicating classical players is $3/4$, the game form of the CHSH inequality. Setting $t=\cos 2\theta$, strict improvement requires $t-t^2>0$, or $0<t<1$. On the stipulated interval this givesThe endpoints give equality with the classical bound. Within this reflected real-basis CHSH strategy, the maximum is $13/16$ at $t=1/2$, namely $\theta =\pi /6$; this follows by completing the square in $t$.

Use deterministic two-qubit entanglement dilution, retaining the specified complex probability amplitudes. Alice implements a quantum instrument on $A$ with Kraus operatorsThe Kraus representation completeness condition holds even for complex $\alpha ,\beta$:To realize this using the permitted quantum gates and a basic measurement, Alice initializes an ancilla qubit $C$ to $|0⟩$. Conditional on her computational-basis state being $j$, she applies to $C$ the unitary matrixEach has orthonormal columns. Therefore $W=|0⟩⟨0{|}_A\otimes V_0+|1⟩⟨1{|}_A\otimes V_1$ is a unitary gate, withA computational-basis measurement of $C$ implements the desired quantum instrument. Its two unnormalized branches on $AB$ areEach has probability $1/2$. Alice sends her outcome $m$ as one classical bit. For $m=0$, both parties keep their qubits unchanged. For $m=1$, both apply a Pauli X gate, givingThus both outcomes produce the exact target using one classical bit and local operations. The construction includes $\alpha =0$ or $\beta =0$ and arbitrary relative quantum phases; it requires no quantum channel between the parties.

Combine the hypothetical protocol with superdense coding. Before a message is chosen, Alice and Bob share a further Bell pair $|{\varphi }_{+}{⟩}_{QR}$, with $Q$ at Alice and $R$ at Bob, in addition to any resources needed for the hypothetical quantum teleportation protocol. To encode two classical bits $u,v$, Alice applies the Pauli gates $Z_Q^u{X}_Q^v$, preparingThe four choices are the four mutually orthogonal Bell states. Alice now uses the hypothetical protocol to teleport $Q$ to Bob using only one classical bit. Its assumed preservation of the joint quantum state gives Bob both $B$ and $R$ inBob performs a Bell-basis measurement. Explicitly, a controlled-NOT gate $B\to R$, followed by a Hadamard gate on $B$, givesA computational-basis measurement therefore recovers both message bits with certainty after only one transmitted classical bit. The initial Bell pairs are shared before the message is chosen and carry no message themselves. This proves the classical communication lower bound for exact qubit teleportation: a perfect protocol preserving an external reference needs at least two transmitted classical bits.

Alice holds the input qubit $Q$ in $|\psi {⟩}_Q=a|0⟩+b|1⟩$ and her half $A$ of a shared Bell pair $|{\varphi }_{+}{⟩}_{AB}$; Bob holds $B$. Alice applies a controlled-NOT gate $Q\to A$, then a Hadamard gate on $Q$. In the system order $Q,A,B$, the initial quantum state isAfter these two quantum gates, direct expansion yields the quantum teleportation identityAlice performs computational-basis measurements on $Q,A$, and sends the two classical bits $m,n$ to Bob. Each outcome has probability $1/4$, independently of the input pure state. Bob applies the indicated Pauli gates: first $X^n$, then $Z^m$, so his total correction is $Z^m{X}^n$. In every branch,This proves exact quantum teleportation using one Bell pair and two classical bits. Alice's original qubit has been measured; the protocol transfers the quantum state without leaving her another copy.

Reference-distribution ambiguity: $\rho$ is not defined in the paper. If it is an arbitrary probability mass function, the printed inequality is false. For instance, choose $p=(1,0)$ and $\rho =(1/2,1/2)$. Every empirical distribution equals $p$, making the printed left side one bit and its right side zero. This is a counterexample for every $n\ge 1$.

Under the consistent interpretation $\rho =p$, the preceding leave-one-out identity for empirical distributions and convexity of relative entropy in its first argument give, for every sample,Deleting any one observation from $n+1$ independent and identically distributed random variables leaves $n$ independent observations with probability mass function $p$. Consequently each ${\hat{q}}_{n,i}$ has the same distribution as ${\hat{p}}_n$. They need not be independent of one another. Taking expected values and using linearity of expectation therefore provesZero coordinates of $p$ are never sampled, almost surely, so the calculation can be restricted to its probability support. In particular the expected values are finite on this finite alphabet.

The discrepancy cannot be removed by silently choosing any fixed reference. Whenever $\rho$ is positive on the probability support of $p$, direct subtraction and $\mathbb{E}{\hat{p}}_n=p$ give the expected relative entropy decompositionThus the valid arbitrary-reference version has $\rho$ on both sides; the printed mixed-reference version has an additional term whose sign prevents the proposed conclusion.

For a discrete memoryless channel with transition probabilities $M(y\mid x)$, the conditional probability of a length-$n$ output given a length-$n$ input factors asThe same transition probabilities apply at each use. Its channel capacity isThe unit is bits per channel use. For finite alphabets the maximum exists by continuity on the probability simplex; with more general alphabets one uses a supremum when appropriate.

An $(m,n)$ channel code consists of an encoder $c:{\mathcal{V}}_m\to {\mathcal{X}}^n$ and a decoder $d:{\mathcal{Y}}^n\to {\mathcal{V}}_m$. It represents each of $m$ messages by $n$ input symbols and recovers a message from the $n$ observed output symbols. Its code rate is $R=({\log }_{2}m)/n$ bits per use. For each message $w$, its conditional error probability is $\mathbb{P}(d(Y^n)\ne w\mid W=w)$; an average error also specifies the message probability distribution, while the maximum error takes the largest conditional error.

Choose noise values $0,2$, giving exactly the outputs $0,1,2,3,4$. The transition matrix, in that column order, isAn input probability mass function $(1/2,1/2,0)$ makes outputs $0,1,2,3$ equiprobable, so $H(Y)=2$ and $H(Y\mid X)=1$. Hence $C\ge 1$ bit per use, as required for comparison with the four-output case.

There is a strict improvement, which can also be computed exactly. Reflection of the input labels $0\leftrightarrow 2$, accompanied by output reflection $y\leftrightarrow 4-y$, leaves mutual information unchanged. Concavity of information entropy makes mutual information a concave function of the input probability mass function for a fixed transition matrix. Averaging an input law with its reflection therefore cannot decrease it. It suffices to considerThe outputs whose labels are even integers have total mass $s$ and conditional probability mass function $(1/4,1/2,1/4)$, with information entropy $3/2$. The outputs whose labels are odd integers have mass $1-s$ and conditional probability mass function $(1/2,1/2)$, with information entropy one. Splitting first by output parity using the chain rule for information entropy yieldsIts derivative is ${\log }_2((1-s)/s)+1/2$, and its second derivative is negative. The unique maximum occurs at $s=\sqrt{2}/(1+\sqrt{2})$, givingThis additional optimization explains the collision pattern: outputs $1,3$ identify input $1$, outputs $0,4$ identify the two extreme inputs, and only output $2$ is ambiguous.

Translate the output alphabet by $-\min (z_1,z_2)$ and put $d=|z_2-z_1|\ge 1$. The reachable outputs becomeFor $d=1$ the two sets overlap in two points; for $d=2$ in one; for $d\ge 3$ they are disjoint. In particular $|\mathcal{Y}|\ge 4$, and choosing noise values $0,1$ attains four.

With rows indexed by inputs $0,1,2$ and columns by outputs $0,1,2,3$, independence and uniform two-point noise giveEvery conditional output distribution has information entropy one bit, so $I(X;Y)=H(Y)-1\le {\log }_{2}4-1=1$. The input probability mass function $(1/2,0,1/2)$ makes all four outputs equiprobable, attaining that bound. ThusUsing a zero-probability input in a channel-capacity maximization is legitimate; it is unrelated to the strictly positive source weights needed for the tree-shape claims in Question 2.

For every input probability mass function, conditional entropy is nonnegative, soTaking the maximum over input laws proves $C\le 1$ bit per channel use. This bound comes from the binary input alphabet itself; no specific transition probabilities or decoder are needed.

There are two possible messages and three channel uses, givingConditional on either transmitted message, a decoding error occurs exactly when at least two of the three bits are flipped. The discrete memoryless channel makes these flips independent, each with probability $\epsilon =1/10$. Their count therefore has a binomial distribution with parameters $3,\epsilon$. Majority-vote decoding of a repetition code givesInterchanging the two bit values leaves the binary symmetric channel and majority decision unchanged, so $\mathbb{P}(\text{error}\mid W=b)=7/250$ as well. Both the maximum conditional error and the average error, for any message prior, are therefore $0.028$. The probability of correct decoding for each message is $243/250=0.972$. These are finite-block error probabilities; a channel-capacity statement alone would not determine them.