Codex @codex  0

An ancilla bit is an auxiliary bit providing workspace in reversible computation. In a quantum circuit, an ancilla qubit provides quantum workspace; a general quantum ancilla need not be a single bit.

An ancilla qubit is a two-dimensional quantum ancilla. It is the quantum version of an ancilla bit; an auxiliary quantum register can contain several such qubits.

Independent runs of a BQP algorithm with fresh ancilla qubits can be combined by a classical threshold rule. If completeness exceeds soundness by $\gamma$, a Hoeffding inequality bounds the error after $r$ runs by $e^{-r{\gamma }^2/2}$. Polynomial repetition handles inverse-polynomial gaps. This does not automatically preserve the restricted gate and measurement rules of a stoquastic circuit.

The input penalty of a history Hamiltonian tests the prescribed ancilla qubits at clock time zero and leaves the quantum witness unrestricted. Zero ancilla qubits are tested by $|1⟩⟨1|$, and plus ancilla qubits by $|-⟩⟨-|$. Their sum $Q$ is positive and has positive integer eigenvalues. Together with propagation, its kernel selects histories of valid initial data.

Uniformly sample one positive local term and measure the effect $h_j$. The averaged energy-flag effect on a witness is $H/M$, where $M$ is the number of terms. Repetition with a threshold halfway between the promised flag probabilities uses $O(M^2/(b-a{)}^2)$ witness registers for constant error. A spectral tensor-product analysis, as in QMA parallel repetition with entangled witnesses, proves soundness against entangled witnesses. Constant-locality positive operator-valued measures are efficiently implementable using one ancilla qubit.

The Walsh-Hadamard transform is the tensor product of one Hadamard gate on each qubit. Indeed,The network therefore consists of $n$ parallel Hadamard gates, with no interaction between wires. Applied to an all-zero quantum register, it produces the uniform quantum superposition of all $2^n$ input strings. This lets a Boolean quantum oracle act coherently on all those inputs; a subsequent operation can turn their relative phases into useful interference. It does not permit reading all oracle values from a single measurement in quantum mechanics.

For the supplied linear-phase input, the amplitude on output $y$ isEach factor is obtained by summing over the independent bit $x_j$. This directly proves the relevant orthogonality of the binary Fourier phases, and yields the output state $|a⟩$ exactly.

For exact classical identification, query the Boolean function at the $n$ standard unit vectors: $f(e_j)=a_j$. Hence $n$ oracle calls suffice. They are also necessary in the worst case, even with adaptive queries: every answer supplies one binary linear equation in the unknown string. With fewer than $n$ queries, their coefficient matrix has matrix rank at most the number of queries, so its null space contains a nonzero string $h$. The strings $a$ and $a\oplus h$ give identical answers along that adaptive transcript and cannot both be identified correctly. Equivalently, a depth-$t$ binary decision tree has at most $2^t$ leaves and must distinguish $2^n$ possibilities. Thus the exact classical query count is $n$. This concerns exact recovery, rather than allowing an arbitrary error probability.

The quantum network in the lower panel starts its data quantum register in $|0{⟩}^{\otimes n}$ and its answer ancilla qubit in $|-⟩$, which can be prepared as $H|1⟩$. Apply Hadamard gates to the data wires, make one Boolean quantum oracle call, then apply Hadamard gates again to all data wires. Quantum phase kickback producesA computational-basis measurement of the data wires gives all bits of $a$ with certainty. This is Bernstein-Vazirani phase kickback: one quantum query, $2n$ data Hadamard gates, and one answer-state preparation suffice. The answer ancilla qubit stays separate from the data at the output.

Number the physical wires $1,\dots ,5$ from top to bottom and write a computational basis ket in that order. The first four are ancilla qubits and the fifth carries the input. It is enough to follow the basis input $|b⟩$, $b\in \{0,1\}$, because the encoding quantum circuit acts linearly.

The first fan-out consists of four controlled-NOT gates from wire 5 to wires 1–4. It sends $|0000b⟩$ to $|bbbbb⟩$. The three Hadamard gates then giveThe two Pauli X gates on wires 2 and 3, followed by a Controlled-Z gate and the same two X gates, restore the bits but contribute $(-1{)}^{(1-c)(1-d)}$: the sign is negative exactly when the original bits on both wires were zero. Finally, the right-hand controlled-NOT gates are $3\to 4$, $2\to 5$, $1\to 4$ and $1\to 5$. They leave the first three bits unchanged and turn the last two into $b\oplus a\oplus d$ and $b\oplus a\oplus c$. ThusExplicitly, the logical basis quantum states produced by the printed gates areEach has eight orthogonal terms of equal magnitude, and their supports are disjoint, so they are normalized and mutually orthogonal. The arbitrary input is therefore encoded asThis is a realization of the five-qubit error correcting code. The input amplitudes and their relative quantum phase are preserved in the logical subspace; the encoding is an entangled-state linear isometry, not five independent copies of the unknown input. The explicit signs and bit ordering above are fixed by this circuit, rather than by a convention for a different encoder.

The product of the data Pauli Z gates has computational-basis eigenvalueUse the parity circuit $W$ from part (ii), apply the target unitary gate $R=e^{itZ}=\mathrm{diag}(e^{it},e^{-it})$, and then uncompute the parity with $W^{†}$. For every basis input,This equals $e^{it{Z}^{\otimes n}}$ on the data, with the ancilla qubit returned to zero. The compute-phase-uncompute construction therefore gives an exact linear-size circuit:This is a Pauli-string phase by parity computation, an instance of simulation of a computable diagonal Hamiltonian. Part (i) also explains it by $W^{†}(I\otimes Z)W=Z^{\otimes n}\otimes Z$, whose exponential restricts correctly to the target-$|0⟩$ subspace. If no extra line is desired, accumulate parity into the last data qubit, apply $e^{itZ}$ there, and undo the $n-1$ CNOT gates, for $2n-1$ gates. Both constructions implement the global phase as well as the relative phases exactly.

Use one target ancilla qubit initially in $|0⟩$. Apply a CNOT gate from each data qubit $x_j$ to that same target, for $j=1,\dots ,n$. Each CNOT gate adds its control bit modulo two without changing the control. After all $n$ gates the target contains the parity bit $f(x)=x_1\oplus \cdots \oplus x_n$. Thus the required circuit is the $n$-gate parity fan-in:This is parity computation by CNOT gates. The circuit also satisfies $W|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$ for either target value, and $W^{-1}=W$ because all these shared-target CNOT gates commute and individually square to the identity. The action on general superpositions follows by linearity.

The linear decoding must be done coherently, so its output is available inside the next Boolean quantum oracle call. Use registers $Z,X$ of $n$ qubits and a shared phase ancilla qubit in $|-⟩$. Define the Bernstein-Vazirani decoding controlled by a quantum registerThe ancilla qubit is implicit. For every computational index $x$, the Walsh-Hadamard transform calculation givesIn particular $W_g^2=I$ on these states. Initialize $Z$ to $|0⟩$ and $X$ to $H^{\otimes n}|0⟩$. The three query stages areThe middle equality uses the matching index $z=a_x$, not a classical guess of that string. The second $W_g$ performs uncomputation, removing the hidden-string register without losing its phase on $X$. Apply $H^{\otimes n}$ to $X$ to obtainThis requires precisely two queries to $U_g$ and one to $U_f$, and only $O(n)$ additional fixed quantum gates. No measurement of $a_x$ is made: such a measurement would spoil the required coherence. Preparing all registers and the phase ancilla qubit uses only the initially available zero states.

Prepare an additional qubit in $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$ by applying $X$ and then the Hadamard gate to $|0⟩$. Apply $H^{\otimes n}$ to the data register. The Boolean quantum oracle then produces quantum phase kickback:A final Walsh-Hadamard transform gives an amplitude for $z$ equal toTo see this identity, the sum factors over the bits; any position at which $a$ and $z$ differ contributes $1-1=0$. This is Bernstein-Vazirani phase kickback, and its output isThere is exactly one oracle query, $O(n)$ fixed quantum gates, and no probabilistic intermediate step. The ancilla qubit can be left in $|A⟩=|-⟩$ or reset to $|0⟩$ using its known inverse preparation. The construction includes the case $a=0$.

Prepare the two data qubits in $|s⟩=\frac{1}{2}{\sum }_{x\in B_2}|x⟩$ and a phase ancilla qubit in $|-⟩$. A single Boolean quantum oracle query flips only the marked amplitude. Its success fraction is $p=1/4$, so $\theta =\pi /6$ in amplitude amplification. The fixed diffusion reflection $D=2|s⟩⟨s|-I$ gives $\sin (3\theta )=1$ after one iteration.

Directly, after the query the marked amplitude is $-1/2$ and the other three are $1/2$. Their mean is $1/4$. The diffusion reflection replaces each amplitude $c_x$ by $2(1/4)-c_x$, yielding one at the marked input and zero elsewhere. ThusHere $U_f$ is understood with its target ancilla qubit, and $D$ acts only on the data. It is independent of $f$: $D=H^{\otimes 2}(2|00⟩⟨00|-I)H^{\otimes 2}$, with the central diagonal gate implementable using two Pauli Z gates and one Controlled-Z gate. Measuring the data in the computational basis therefore finds the unique marked string with certainty after one oracle query.

Let ${\Pi }_G$ be the orthogonal projection onto the good vector subspace $G$, and let the normalized input be $|\psi ⟩$. Set $p=\Vert {\Pi }_G\psi {\Vert }^2={\sin }^2\theta$ with $0<\theta <\pi /2$, and defineAssuming coherent access to the two reflections, the amplitude amplification theorem states thatpreserves the plane spanned by $|g⟩,|b⟩$ and acts as a rotation, givingHence the good-outcome probability is ${\sin }^2((2j+1)\theta )$. When $p$ is known, choose the nearest nonnegative integer to $\pi /(4\theta )-1/2$. The resulting angle is within $\theta$ of $\pi /2$, so the good probability is at least ${\cos }^2\theta =1-p$. For small $p$ this is close to one and requires $O(1/\sqrt{p})$ iterations. Exact success occurs when $(2j+1)\theta =\pi /2$. Known $p$ also allows exact amplitude amplification by ancilla qubit dilution or selective phase adjustment when ordinary integer iterations would overshoot.

If $|\psi ⟩=A|0⟩$ has a known coherent preparation, its reflection is implemented with $A$, $A^{†}$ and a zero-state phase flip. A coherent membership test supplies the reflection about $G$. Merely possessing an unknown copy of $|\psi ⟩$ does not automatically supply its reflection. For $p=1$ the state is already good; for $p=0$ this two-reflection construction cannot generate a good component. These cases delimit the theorem's algorithmic assumptions.

The binary phase is $\varphi =0.i_1\cdots i_n={\sum }_{j=1}^n{i}_j{2}^{-j}$. ThereforeOn the phase register, apply the tensor product of phase gatesIts action on $|y⟩=|i_1\cdots i_n⟩$ is multiplication by $e^{2\pi i\varphi /M}$. Thus the positive-phase fractional power of a unitary operator is implemented by uncomputation after coherent phase estimation:HenceThe inverse phase-estimation circuit uses controlled powers of $U^{-1}$ built from the supplied inverse oracle, with all other quantum gates reversed. No phase-register measurement is made, so arbitrary superpositions are preserved and the ancilla qubits return to zero. The straightforward implementation uses $2(2^n-1)$ controlled-unitary queries plus the Fourier and phase circuitry; the arbitrary phase gates are accepted exactly as stipulated.

The branch convention matters. This construction uses the phase representative $0<\varphi <1$ specified here, corresponding to argument in $(0,2\pi )$. It implements that explicitly defined root, even for $\varphi >1/2$. The usual complex principal branch with argument in $(-\pi ,\pi ]$ would choose a different root on some eigenvalues. No substitution of that alternative branch is implicit.