Quantum algorithms manipulate amplitudes rather than probability distributions alone. Amplitudes can cancel before measurement, while measurement returns a classical outcome. Keeping these two operations distinct is necessary for understanding both algorithmic interference and quantum communication.
States, gates and measurement
Definition 1.1.1
(Pure qubit state and phase)
A pure qubit state is a unit vector in , with . The computational basis vectors are and . Two unit vectors differing by a common phase represent the same pure physical state; a relative phase between coefficients can affect later measurement probabilities.
A computational-basis measurement produces 0 with probability and 1 with probability . Conditional on the observed outcome, the state becomes the corresponding basis vector. More generally, for orthogonal projectors satisfying , the outcome has probability , and its post-measurement state is when this probability is nonzero.
Definition 1.1.2
(Unitary gate)
A closed-system gate is represented by a unitary matrix , meaning . This preserves norms and inner products. Important examples are
exchanges the basis states, changes the sign of the amplitude, and exchanges the computational and bases. Applying to gives , whereas applying it to gives . Both inputs have equal computational-basis measurement probabilities; their relative signs are revealed only after a basis change. This is interference, not a claim that one measurement reads out both coefficients.
Bras, complex inner products, and measurement in another basis
Definition 1.1.3
(Bra and complex inner product)
The calculation of an amplitude uses a complex inner product, so its order matters. For a column ket , the corresponding bra is its conjugate transpose . Thus and . In particular, is real and nonnegative. Transposing without conjugation would give the wrong length for vectors with imaginary entries.
Proposition 1.1.4
(Measurement in an orthonormal basis)
Let be an orthonormal basis of , and let be normalized. Its expansion and measurement probabilities are
Proof
(Reading off coefficients)
To see why, the coefficients in any expansion satisfy by orthonormality. The outcome projector is , so its Born probability is . The same expansion shows . These formulas require an orthonormal measurement basis; merely choosing two normalized, nonorthogonal vectors does not give these projectors a sum equal to the identity.
Worked example 1.1.5
(Measuring in a complex basis)
Set and . They are orthonormal: in particular . For input , the amplitudes are and ; the first outcome is certain. If the in the bra were not conjugated, the calculation would instead give the wrong answer. Direct computational-basis measurement of this same input gives each outcome probability : the measured basis matters.
Quick check
(For input , find both probabilities in the basis and the state after outcome 1.)
Compute for each .
Solution · Answer
Both amplitudes equal , so the probabilities are each; after outcome 1 the normalized state is . Outcome probabilities alone do not reconstruct the state left by a measurement.
A phase experiment and two successive measurements
Consider the family , where is real. Measuring directly in the computational basis gives 0 and 1 with probability each, for every . This does not mean that all these states are identical. Apply before measuring instead. Linearity gives
The two paths contributing to each outcome are added as amplitudes before squaring. For the result is certainly 0; for it is certainly 1. A common factor multiplying the whole input multiplies each output amplitude by the same factor and changes neither probability. The relative phase can therefore be observable even though the global phase is not. One measurement setting need not distinguish every phase: for example and have the same two probabilities above.
Now suppose a computational-basis measurement is made before , and its result is ignored. Conditional on result , the post-measurement state is ; this experiment has two classical branches, each of weight . In either branch the later followed by a computational measurement gives 0 with probability . The law of total probability therefore gives , regardless of . For this differs from the certain 0 obtained without the first measurement. The intermediate measurement changes the experiment, even when nobody records its outcome.
Proposition 1.1.6
(Two successive ideal projective measurements)
More generally, for a normalized pure state , an ideal projective measurement followed immediately by another ideal projective measurement gives
Proof
(Conditioning on the first outcome)
Put . For , the conditional state is , so the conditional probability of is . Multiplying by gives the joint formula. A zero-probability branch contributes zero without requiring a conditional state; summing over gives the second formula. The formula assumes the stated ideal projective update, with no other operation between the measurements.
Common mistake
(A forgotten outcome is not a coherent superposition)
If the first measurement is omitted, the probability is instead . The cross terms between different can then survive. It is generally wrong to sum the branch probabilities as though the first measurement had taken place. Conversely, once it has taken place and its outcome is forgotten, adding the branch amplitudes would incorrectly restore coherence.
Quick check
(Start with , measure in the basis and forget the result, then measure in the computational basis. What is the chance of obtaining 1?)
Use total probability over the forgotten outcome.
Solution · Answer
It is : either first outcome has probability , and each conditional state yields 1 with probability . Without the intermediate measurement, the chance would be 0. Repeating the same ideal projective measurement, by contrast, returns the same outcome with probability one, since .
Composite systems and entanglement
Two qubits have state space and ordered basis . A product state has amplitudes formed by multiplying those of the factors. The controlled-NOT gate sends to . Here is addition modulo two: and . It is unitary because it permutes an orthonormal basis.
Calculating with two registers
The order of the two factors matters. Write , with the first label belonging to Alice and the second to Bob. Distributivity gives
For example, . A gate on the first register and on the second acts by , extended linearly. Thus , while . The location of changes the answer. A general two-qubit gate need not be a product ; controlled-NOT is one such gate.
Theorem 1.1.7
(Product-state test)
For a nonzero pure two-qubit vector , form the coefficient matrix . The vector is a product exactly when .
Proof
(A rank-one coefficient matrix)
If , then is an outer product and its determinant is zero. Conversely, if and , its two columns are linearly dependent, so for nonzero column vectors . The entries therefore factor as . If is normalized, then ; rescaling the two factors yields normalized individual states without changing their product. The transpose here is ordinary transpose, not conjugate transpose: the statement factors coefficients, not inner products.
Worked example 1.1.8
(Testing two states for product form)
For instance, has matrix and factors as . In contrast, has determinant and cannot factor. This test applies to a pure vector, not directly to a mixed density operator: a mixed state can be separable as a mixture of product states without being a single product state.
Quick check
(Is a product state? What are and ?)
Compute the coefficient determinant.
Solution · Answer
Its coefficient determinant is , so it is entangled. , whereas .
Starting from , apply to the first qubit and then controlled-NOT. The result is the Bell state
It is not a product. Indeed, if equaled it, the coefficients would satisfy and , which is impossible because the first two equations make all four factors nonzero. Measuring both qubits in the computational basis gives 00 and 11 with probability each. The individual results are random but perfectly correlated.
Common mistake
(Correlation is not entanglement)
Correlation alone does not establish entanglement: a classical mixture of 00 and 11 has the same computational-basis statistics and differs in other measurements.
Definition 1.1.9
(Density operator and reduced state)
A density operator describes both a pure state and a classical mixture . It is positive semidefinite and has trace one. A projective outcome has probability . The reduced state of subsystem A is , defined by and linearity. For the Bell state, , although the joint state is pure. Discarding the second qubit removes the off-diagonal terms between and ; it does not turn the joint state into a product.
No universal cloning
Theorem 1.1.10
(No universal cloning)
No unitary can copy every unknown pure qubit state into a fixed blank register: there is no satisfying for all unit .
Proof
(Linearity breaks the copy)
The claimed action on and would give and . Linearity then gives . But , a different state.
Counterexample mode
CNOT copies only basis states
A tempting repair is to say that controlled-NOT with a blank target copies any qubit. It copies the basis states, and , but on it gives , whereas a copy would be . The overlap of the two is , so the output is not a copy. This does not prohibit copying a known orthogonal basis; what is impossible is a single device that copies arbitrary unknown states.
Teleportation step by step
Alice holds and one half of ; Bob holds the other half. In order, Alice applies controlled-NOT from her unknown qubit to her Bell qubit and then to her unknown qubit. The resulting three-qubit state is
Each two-bit measurement outcome has probability . Alice sends the two classical bits to Bob. For outcomes 00, 01, 10, 11 he applies respectively , obtaining in every case. In the last case ; the order of operators matters. The original state is not retained by Alice, and Bob cannot know which correction to apply without the classical message. Teleportation therefore neither clones an unknown state nor supplies faster-than-light communication.
Theorem 1.1.11
(Teleportation correctness)
Let Alice hold and one half of , apply controlled-NOT from her unknown qubit to her Bell qubit and then to her unknown qubit, and measure both. Each outcome occurs with probability for every , and Bob's qubit is then in the state . Applying returns .
Seeing the four branches form
Proof
(Tracking the amplitudes)
The four-term identity above is worth deriving once: it makes clear which qubit is measured and where the correction comes from. Order the registers as , where is Alice's input, is her half of the Bell pair, and is Bob's half. Before Alice's gates the state is
Controlled-NOT has control and target : it flips the middle bit only when the first is 1. The state becomes
Now apply and to the first bit, then collect terms by Alice's two bits. The result is
Reading the parentheses from right to left as operator actions identifies them as , , and . Each has norm one because and are unitary. Consequently each outcome has probability , even when and are complex. After outcome 11, for example, the correction is , since the rightmost operator acts first and .
Proof X-ray
Where the classical bits do their work
The proof is a bookkeeping identity that uses three inputs. Linearity lets and controlled-NOT act term by term on , so and ride along unchanged into Bob's register. The shared Bell pair correlates Alice's second qubit with Bob's qubit, which is why the second bit selects the Pauli . The one non-obvious move is the final regrouping by Alice's two bits: the Hadamard gives the part of the first qubit a minus sign, which becomes the that appears whenever that bit is 1. Because and are unitary, every branch has norm one, so every outcome has probability whatever are, and Alice's bits carry no information about . Without the two classical bits, Bob cannot know which Pauli to undo.
Worked example 1.1.12
(Teleporting a state with a relative phase)
Let and suppose Alice obtains 11. Bob's normalized conditional state is . Applying gives back . Alice's outcome was random; it did not reveal the value of the relative phase.
Before the classical message
Proposition 1.1.13
(Bob's state before the message)
Write , where . If Alice measures but Bob has not learned the result, his state is the mixture of the four conditional states, not a sum of their state vectors:
Proof
(Canceling the off-diagonal terms)
Indeed, , , and . Their off-diagonal entries cancel and each diagonal sum is . Thus any measurement Bob makes before receiving the message has statistics independent of . After he receives the two bits he can select the correct inverse for that particular branch. This distinction is the role of the classical communication; shared entanglement alone does not transmit the unknown state.
Quick check
(For input , what can Bob infer from a computational-basis measurement before the message, and what happens after Alice reports 01?)
Use the branch formula.
Solution · Answer
Before the message, both outcomes have probability . On the 01 branch Bob holds ; after applying he holds . In general, before correction he holds , and applying gives . Knowing the branch changes which correction he can choose, not the probabilities in the earlier unconditioned experiment.
Practice and solutions
Quick check
(Compute .)
Apply the gates from right to left.
Solution · Answer
, , and ; in fact .
Quick check
(Find the reduced density operator of the first qubit of .)
Trace out the second qubit of the outer product.
Solution · Answer
Expanding the outer product and tracing out the second qubit leaves .
Three CNOTs implement SWAP
This note uses ordered tensor products. In , the first factor is qubit 1 and the second factor is qubit 2. For bits , define
The identity below is used later in the QFT note, where qubit order must be reversed.
Theorem 1.1.14
(Three CNOTs implement SWAP)
The gate order , then , then implements .
Proof
(Following a basis state)
In actual time order,
The last two steps use and . In an operator product, the rightmost factor acts first, so we write . This product reads the same in both directions, but the convention matters for later circuits that are not symmetric.
Worked example 1.1.15
(Following the input 01)
For example, the input passes through three states. It stays after the first gate, because the control is . It becomes after the second gate and after the third.
Why basis states suffice. Both sides are linear operators. They agree on the basis , so they agree on every superposition .
Suppose the pair is entangled with a reference register . The circuit then acts as , which is also determined by its action on basis states. With factor order ,
The correlation with moves from to .
Subtle points.
- SWAP exchanges the contents of two registers. It does not copy an unknown state, so it is consistent with the no-cloning theorem.
- Three CNOTs suffice here. Other gate sets may implement SWAP differently, so do not treat three CNOTs as a required count in every gate model.
Quick check
(Compute the output for the input .)
Expand the input in the computational basis.
Solution · Answer
First expand: . By linearity, and . The output is therefore
The two tensor factors have exchanged positions.
Global phase under control
Assumptions. and are specified unitary matrices on a target register, with . For a specified matrix , the controlled version is .
On its own, cannot be distinguished from . For every target density operator ,
so the two matrices induce the same channel.
Their controlled versions differ when . Since ,
The factor acts only in the branch where the control is . It therefore becomes a relative phase between the joint control–target branches; the reduced control state alone need not reveal it. Phase estimation relies on this effect later.
This does not contradict the rule about global phase. The phase is global for ; when , it is relative between branches of the larger operation . The controlled gate, including its relative-phase convention, must therefore be specified. If we know an unknown device only as a channel, that knowledge does not fix a canonical phase to control. We do not assume that an arbitrary black-box can be controlled.
Quick check
(Let and , with the control initially and the target an arbitrary normalized . After , the control becomes . Compare the statistics of and in each of three measurements.)
Compute each probability separately.
Solution · Answer
- Computational basis. The probabilities are each, the same as for .
- After . , so each outcome has probability . For , the outcome is with probability .
- In the basis. The outcome has probability for . For it has probability .
The states and are not orthogonal, so no single-shot measurement separates them perfectly. The choice of basis decides which statistics reveal the phase.