Three ideas recur in quantum computing: interference can reveal a global promise about a function, entanglement can produce correlations beyond a classical shared-randomness model, and redundant encoding can protect quantum information without reading its unknown amplitudes. Each claim depends on a precise model. We develop one example of each and identify what it does not establish.
Simon’s hidden XOR mask
Definition 2.5.1
(Simon’s promise and oracle)
A function satisfies Simon’s promise if there is a nonzero such that
The goal is to find using queries to the reversible oracle . Below, denotes the bitwise dot product modulo , and is the orthogonal subspace over .
Thus every function value has exactly two preimages, separated by the same unknown mask. The oracle is a permutation of basis states and hence unitary, even though itself is two-to-one.
Proposition 2.5.2
(Simon samples lie in the orthogonal subspace)
Start with , apply to the first register, query , apply to the first register again, and measure it. The outcome is uniformly distributed on the -dimensional subspace of .
Proof
(Pairing preimages and canceling by parity)
After the first Hadamards and the query the state is . Measuring the second register produces some value ; conditional on that value, the first register is
Since and modulo , the amplitude of after the second layer of Hadamards is
It vanishes when and has squared modulus when . The same distribution arises for every value of the second register, so each run samples uniformly from the -dimensional subspace . Measuring the second register is useful for this derivation but can be omitted: discarding it gives the same distribution on the first register.
Proof X-ray
Where the hidden mask enters
The promise is used exactly once, to say that the two preimages of a value are and for the same . Bilinearity of the dot product turns the shift by into the relative sign , and the unknown representative appears only in the global sign , which cannot affect probabilities. This is why the distribution does not depend on which value was seen.
The Hadamard transform cancels precisely those outcomes for which the relative sign is negative; the remaining samples are equations, not the mask itself. Without the promise there is no common and no cancellation pattern, as the counterexample below shows. Repetition is necessary until the samples span and identify its one-dimensional orthogonal complement.
Repeat to obtain linear equations , then solve them by Gaussian elimination over . The sample gives no information, and repeated samples may be dependent.
Proposition 2.5.3
(Recovering the mask from samples)
If the samples span , then is the unique nonzero solution of for all . For independent samples, the probability that they fail to span is at most .
Proof
(Complement and union bound)
If the samples span , any solution is orthogonal to all of . Over the dot product is nondegenerate, so has dimension and contains ; hence it is , and the unique nonzero solution is the mask.
If the samples do not span , they lie in a proper subspace, hence in the kernel of some nonzero linear functional on . There are such functionals. For a fixed one, the kernel has half the elements of , so each uniform sample lies in it with probability , and all independent samples do so with probability . A union bound over the functionals gives the claim.
Thus queries give constant success probability, which can be increased by additional samples. A classical query lower bound refers to the same promised black-box model; the query count alone does not account for implementing a particular oracle.
Worked example 2.5.4
(Samples for a three-bit mask)
For and , the possible outputs are 000, 001, 110, 111, each with probability . Independent equations from and give and ; the only nonzero solution is 110. One run does not generally determine the mask.
Common mistake
(A single sample is not the mask)
A sample only satisfies ; it is an equation about , not itself. In the three-bit example the sample is perfectly valid, yet it differs from , and the sample carries no information at all. The sample happens to equal the mask only by accident, as in the two-bit example below. Output a mask only after the equations single out one nonzero solution.
A complete two-bit oracle calculation
Worked example 2.5.5
(Two-bit oracle, full circuit)
Take and . Its table sends to and to . Thus its two-element fibers differ by , as the promise requires. In a hidden-mask problem the learner does not receive this table; we display it here to check the circuit.
Starting with both registers in , the first Hadamards and oracle give
The first ket in each product is the input register. Applying to that register maps to itself and maps to . The resulting joint state is therefore
No or occurs in the first register. Both and occur with probability : for each, the two associated output-register states are orthogonal, so their squared amplitudes add. The sample gives ; together with the promise , it determines . The sample imposes no restriction. Notice that the sample happens to equal the mask in this example; this is not a general rule.
With fresh preparations and independent runs, the probability of having seen at least once after runs is . Thus three queries give probability of conclusively identifying the mask from the sampled equations in this example. This probability is over measurement outcomes, not over a random choice of ; it also presumes that the learner uses the nonzero-mask promise. A strategy that guesses when all samples are zero has a different success probability, depending on how the unknown mask is modeled and how the guess is chosen.
Quick check
(Instead let . Find its mask and the two possible samples. If the first two independent samples are both , has the sample data alone identified the mask?)
Solution · Answer
The fibers are and , so . The condition gives or , each with probability . Two zero samples give only the equation ; all three nonzero two-bit masks remain compatible with those sample equations. The displayed function table identifies the mask, but the algorithm is assumed to have oracle access rather than the table.
The promise cannot be dropped silently. The next example runs the same circuit on a function that is not two-to-one and shows that the samples then do not determine any mask.
Counterexample mode
Without the promise there is no mask to find
Claim: whatever is, the circuit samples only from some hyperplane with . Take , so and ; this is not two-to-one. With probability the second register shows , and the first register is then . After the amplitudes of are divided by , giving probabilities . With probability the second register shows , the first register is , and all four outcomes have probability . Overall the outcomes occur with probabilities . All four strings occur, so the samples span and the only solution of for all samples is . No nonzero mask is consistent with the data. The proposition above needs the two-to-one promise.
CHSH and the meaning of nonlocal correlations
Definition 2.5.6
(Local strategies and the CHSH expression)
In the CHSH experiment, Alice and Bob separately receive input bits and return signs . A deterministic local strategy assigns each of in advance. A local hidden-variable strategy is a probabilistic mixture of deterministic ones, with input choices independent of the shared hidden variable and each party’s output depending only on its own input and that variable. The CHSH expression is
Theorem 2.5.7
(Classical CHSH bound)
For every local hidden-variable strategy, .
Proof
(Deterministic assignments and averaging)
Since each of is , exactly one of and is nonzero, and it equals . The other bracket is , so for every deterministic assignment. A local hidden-variable strategy is a mixture of these, and the expectation of a quantity of absolute value has absolute value at most .
Now share and take observables
Each is Hermitian with eigenvalues .
Theorem 2.5.8
(A quantum strategy exceeding the classical bound)
With these observables on , the CHSH expectation is .
Proof
(Four correlators)
Substituting the observables,
On the expectations of and are , so .
For uniformly random inputs, the game rewards equal output signs except when , when it rewards opposite signs. Its winning probability is : the quantum choice wins with probability , versus at most for classical local strategies.
Common mistake
(Nonlocal correlation is not signaling)
The violation rules out the specified local hidden-variable explanation, not the no-signaling principle. Each local marginal here is uniformly random; the input chosen on the distant side cannot be read from it alone. Comparing correlations requires classical communication, so the violation cannot be used to send a message.
Protecting one qubit from a bit flip
Definition 2.5.9
(Three-qubit bit-flip code)
The code encodes into three qubits as
An encoding circuit starts with and uses controlled-NOT from the first qubit to each of the other two. Its syndrome is the pair of eigenvalues of the commuting parity observables and .
Common mistake
(Encoding is not copying)
The encoded state is not three copies of : the result is generally entangled, whereas three copies would contain eight basis terms, with coefficients such as . Copying an unknown state is impossible, which is exactly why this redundancy is built from correlations.
Suppose the error is promised to be either no error or , a single bit flip on qubit . The eigenvalue pairs for the four cases are:
| Error | ||
|---|---|---|
| None | ||
Theorem 2.5.10
(Single bit-flip correction)
For each of the four possible cases the encoded state is a joint eigenvector of and with the eigenvalues in the table, and these pairs are pairwise distinct. Applying the that the syndrome names restores .
Proof
(Parities of a codeword and its complement)
A basis state is an eigenvector of with eigenvalue and of with eigenvalue . The two terms of are bit-complements of each other, and complementing all bits leaves each pair-parity unchanged. Hence both terms have the same syndrome, and the state is an eigenvector. Reading off one term: gives ; gives ; gives ; gives . The four syndromes are distinct, so the syndrome determines which occurred, and since applying it again restores . The syndrome is the same for every , so measuring it reveals nothing about them.
Worked example 2.5.11
(Syndrome of a flip on the first qubit)
For , the term has and . The term has and . Both terms give the syndrome , which is the row for , and applying restores . In the edge case of no error both terms give and no correction is applied.
For , both basis terms have eigenvalue for both parities. The syndrome therefore identifies the error without distinguishing the and terms; applying restores the encoded state. The syndrome measurement reveals which promised error occurred, not the encoded computational-basis value.
This code corrects one bit flip, not an arbitrary single-qubit error.
Counterexample mode
The bit-flip code does not correct phase errors
Claim: the three-qubit code restores the encoded state after any single-qubit error. Take . Then , whose terms have the same two syndromes as the uncorrupted state, so the decoder applies no correction and the relative phase stays changed. For , with , this turns the encoded plus state into an orthogonal encoded minus state. The claim holds only under the promise that errors are bit flips. Correcting general errors requires a code and syndrome scheme that also detects phase errors, and fault-tolerant operation additionally requires controlling errors introduced by encoding, gates and syndrome extraction.
Practice and solutions
Quick check
(In Simon's promise with and , list the possible samples .)
Solution · Answer
The condition over gives 000, 010, 101 and 111, each with probability .
Quick check
(For deterministic signs and , simplify the CHSH expression. Can any choices of exceed in absolute value?)
Solution · Answer
, so its absolute value is exactly 2 for every choice of .
Quick check
(What syndrome results from in the three-qubit code, and what correction restores the state?)
Solution · Answer
The parity pair is ; apply again, using .