Codex @codex  0

Quantum no-signalling says that, without communicating a measurement outcome, any local trace-preserving operation performed on subsystem $A$ leaves all outcome probabilities for measurements on subsystem $B$ unchanged; equivalently, it leaves the reduced density matrix ${\rho }_B$ unchanged.

The two Bell states are orthogonal. Applying the inverse Bell-state preparation circuit, namely a Controlled-NOT gate from $A$ to $B$ followed by a Hadamard gate on $A$, givesA computational-basis measurement therefore distinguishes them perfectly, soIf only $B$ is accessible, however,Every measurement on $B$ consequently has the same outcome distribution under both hypotheses. With equal prior probabilities no information is available, andthe error probability of a random guess.

Apply a Pauli X gate and then a Hadamard gate to the third qubit, and apply Hadamard gates to the first two. This preparesOne application of the Boolean quantum oracle now gives, by quantum phase kickback,The answer qubit is unentangled and may be ignored. If all three qubits must be restored to the displayed register form, applying $H$ and then $X$ to the answer qubit maps $|-⟩$ back to $|0⟩$. Thus the first register is exactly $|f⟩$ after one use of $U_f$.

The printed sum contains $Z_n$ although the stated labels end at $n-1$. We use the natural periodic convention $Z_n=Z_0$, with $n\ge 3$. If an open chain was intended, omitting the final term gives the same asymptotic bound.

Set $H_j=X_{j-1}{Z}_j$, with indices modulo $n$, and implement the product-formula Hamiltonian simulationEach factor acts on two qubits, so it is a two-qubit unitary operator. More explicitly, if $a=j-1$, $b=j$, and $C_{a\to b}$ is a controlled-NOT gate,where ${\mathsf{H}}_a$ is a Hadamard gate. This gives a constant number of one-qubit and two-qubit gates per factor; one-qubit gates can also be viewed as two-qubit gates tensored with the identity.

The spectral norm obeys the triangle inequality, submultiplicativity of the operator norm, and invariance under multiplication by unitary operators. In particular, the telescoping bound for products of operators gives $\Vert V^k-W^k\Vert \le k\Vert V-W\Vert$ for unitary $V,W$. The first-order unitary product-formula error bound consequently yieldsOnly neighboring terms can have a nonzero commutator, because all other supports are disjoint. There are $n$ neighboring unordered pairs, and $\Vert [H_j,H_l]\Vert \le 2\Vert H_j\Vert \Vert H_l\Vert =2$. Thus $\Vert U-\tilde{U}\Vert \le n/k$. Choosing $k>n/\epsilon$ givesThe coarser bound that counts all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs also proves the often-used $O(n^3/\epsilon )$ construction. Locality improves that cubic estimate to the quadratic bound above; neither assertion is a lower bound on the best possible circuit.

Write the normalized input as $|b⟩={\sum }_j{\beta }_j|u_j⟩$, where $A|u_j⟩={\lambda }_j|u_j⟩$ and ${\lambda }_j>0$. Use a data register, an $n$-qubit eigenvalue register, and a flag quantum ancilla. Begin with $|b⟩|0^n⟩|0⟩$.

Apply exact quantum phase estimation to $e^{2\pi iA}$. Its controlled evolutions and inverse quantum Fourier transform produceApply the HHL controlled reciprocal rotation, with $0<c\le {\lambda }_{\min }$:The function of ${\ell }_j$ is computed by quantum arithmetic; the rotation is a quantum variable rotation. On a zero eigenvalue label with no input amplitude, define any unitary action, for example no rotation.

Run the inverse phase-estimation circuit. Because each amplitude multiplier depends only on ${\lambda }_j$, the eigenvalue register is reset to $|0^n⟩$ on both flag branches. Measuring the flag and conditioning on outcome one leavesThe successful unnormalized branch is $c{A}^{-1}|b⟩$, giving the probability in the preceding part. The operations independent of $A,b$ are the Hadamard gates preparing the phase register, the inverse quantum Fourier transform, the reversible reciprocal/angle arithmetic, the controlled fixed-angle rotations, and the final flag measurement. Uncomputation removes all arithmetic workspace; the $A$-dependent controlled evolutions and the $b$-dependent state-preparation circuit supply the input-specific operations.

The controlled-NOT gate sends $|0x⟩$ to $|0x⟩$ and $|1\bar{x}⟩$ to $|1x⟩$. HenceSince the Hadamard gate satisfies $H^2=I$,

Starting from the $n$-qubit computational basis state $|0{⟩}^{\otimes n}$, apply one Hadamard gate to every qubit. Since $H|0⟩=(|0⟩+|1⟩)/\sqrt{2}$,Thus parallel Hadamard gates prepare the uniform quantum superposition.

The Hadamard gate conjugates the Pauli X gate into the Pauli Z gate:When the control qubit is $|0⟩$, all three circuits act as the identity on the target. When it is $|1⟩$, the right-hand circuit acts on the target as $HXH=Z$. It therefore agrees with the Controlled-Z gate on every computational basis state, provingConjugating both sides by $I\otimes H$ and using $H^2=I$ immediately gives the reverse identity

After the first Hadamard gate, the joint state isThe controlled SWAP gate then givesAfter the second Hadamard gate, it is

Starting from $|0^n⟩|0^n⟩$, the first layer of Hadamard gates givesThe Boolean quantum oracle then givesUsing the Walsh-Hadamard transform identitythe final state is

Apply a Hadamard gate to every qubit. The amplitude of $|0^n⟩$ becomesIt equals $1$ in case (I) and $0$ in case (II). A computational-basis measurement therefore returns $0^n$ with certainty in case (I) and never returns it in case (II). This is the Deutsch-Jozsa algorithm.

For the distributed problem, Alice preparesusing one query to her quantum oracle, and sends these $n$ qubits to Bob. Bob applies his phase oracle, producingThe function $h=f_A\oplus f_B$ is constant zero in case (1) and balanced in case (2). Bob applies $H^{\otimes n}$ and measures as above: outcome $0^n$ identifies case (1), while every other outcome identifies case (2), with certainty.

Prepare an ancilla qubit in $|0⟩$. To measure $X\otimes X$, apply a Hadamard gate to each data qubit, apply a controlled-NOT gate from each data qubit to the ancilla, measure the ancilla in the computational basis, and apply a Hadamard gate to each data qubit again. The ancilla records the parity of the two rotated computational-basis bits, so outcome $0$ corresponds to eigenvalue $+1$ and outcome $1$ to eigenvalue $-1$. The data register is projected by $[I+(-1{)}^{s}X\otimes X]/2$, so its complete post-measurement state is retained. For $Z\otimes X$, perform the same ancilla-assisted Pauli measurement but apply the basis-changing Hadamard gates only to the second data qubit.

A $Z$ measurement is a quantum measurement in the computational basis. To measure $X$, apply a Hadamard gate, measure $Z$, and apply another Hadamard gate to the measured qubit. Since $HXH=Z$, this gives the $X$ outcome and leaves the qubit in the corresponding $X$ eigenstate.

Letwhere $H$ is the Hadamard gate. For a computational-basis string $z$, define the phase reflectionThus $I_0$ changes the sign of $|0^n⟩$, while $I_{x_0}$ changes the sign of the marked state.

Conjugating $I_0$ by $H_n$ reflects in the hyperplane perpendicular to $|s⟩$, sois the Grover diffusion operator, the reflection about $|s⟩$. The Grover iteration operatoris the product of two reflections. It acts as a rotation through $2\theta$ in the plane spanned by the marked state $|x_0⟩$ and the normalized uniform superposition of unmarked states, whereIt is the identity up to sign on the orthogonal complement of that plane.

Put $P_1={\sigma }_1\otimes {\sigma }_2$ and $|\psi ⟩=|A{⟩}^{\otimes 2}$. After the first Hadamard gate and the two controlled Pauli gates, the joint state isThe final Hadamard gate changes this toConditioned on ancilla outcome $s\in \{0,1\}$, the normalized data state is therefore

Write the input in the two eigenspaces of $P_1$ aswhere the displayed eigenstates are normalized. A direct PBC measurement giveswith probabilities $|\alpha {|}^2$ and $|\beta {|}^2$. Hence the ancilla circuit and the Pauli measurement have identical outcome distributions and conditional data states after identifying the Pauli outcome with $(-1{)}^s$.

Since the Hadamard gate conjugates $X$ to $Z$,For $n=1$, each exponential is $-I$, soFor $n=2$,Using $XZ=-iY$ givesso one convenient logarithm isBoth products are Clifford operations: the first is the identity and the second is a one-qubit Pauli Y gate up to global phase.

Yes. The states $|{\Phi }^{+}⟩$ and $|{\Phi }^{-}⟩$ are orthogonal, sinceA joint projective measurement in the Bell basis therefore distinguishes them with certainty. Concretely, a controlled-NOT followed by a Hadamard gate converts the Bell basis into the computational basis before measurement.

Apply the gates from left to right. The first Hadamard gate and the first controlled-NOT gate produce the Bell stateThe parallel $Z\otimes H$ gates then produceThe final controlled-NOT has the lower qubit as control; it interchanges $|01⟩$ and $|11⟩$, whose amplitudes here are equal. Thus the output isBy quantum measurement in the computational basis, every basis outcome has probability equal to the squared modulus of its amplitude:

After the first Hadamard gate and the controlled unitary gate, the state isThe final Hadamard gate givesHence the Hadamard test returns one with probabilityIf $U|\psi ⟩=|\psi ⟩$, then $\theta =0$ and the outcome is zero with certainty. If $U|\psi ⟩=-|\psi ⟩$, then $\theta =\pi$ modulo $2\pi$ and the outcome is one with certainty. The single measurement therefore distinguishes the two promised cases exactly.

The operators $X_i$ act on different qubits and therefore commute, soSince $X=HZH$,The scalar $e^{-it}$ is a global phase. Thus each factor uses two Hadamard gates and one phase gate, and applying the factors in parallel or sequentially gives an exact quantum circuit of $\boxed{3n}$ elementary gates.