## Sunday, 30 October 2011

### Quantum Computing #3: Measurement + Review

Previously:
Introduction
Single Qubit Gates
Why One?

When we looked at the state of a single qubit, ψ = α0 + β1, we noted that this vector had to be of unit length, a stipulation encoded in the normalization condition |α|² + |β|² = 1. Similarly when we extended to a 2 qubit system, ψ = α00 + β01 + γ10 + δ11, we maintained the analogous constraint |α|² + |β|² + |γ|² + |δ|² = 1. This was accomplished by only ever applying so-called unitary (magnitude-preserving) matrix operations to the current state.

The reason for this has to do with the method of getting results out of a quantum computer, which is done by the process of measurement. The outcome of a given measurement operation can be any one of the system's basis states. that is, it will be either 0 or 1 for a single qubit system; 00, 01, 10 or 11 for a 2-qubit system; and so on. Which of the basis states actually gets detected depends upon various probabilities, and in fact these probabilities are just |α|², |β|², etc.

So to clarify, when we perform an operation of measurement in the computational basis on an n-qubit system, we are effectively forcing the state vector to settle into one of its 2ⁿ basis states. Taking the 2-qubit case as an example, the result of the measurement will be either
00 with probability |α|²,
01 with probability |β|²,
10 with probability |γ|², or
11 with probability |δ|².
Since these are the only possible outcomes, it's easy to see why the sums of the squares of the coefficients α, β, γ and δ must be unity - after all, there's a 100% probability the outcome will be one of these states!

The measurement operation irrevocably destroys the previously existing superposition of states, leaving only the single basis state that is the result of the measurement. This means that the original state can never be directly observed. All that we can ever know about it comes from the results of destructive read operations.

For example, suppose we prepare a qubit in the 0 state, then immediately make a measurement. What will the outcome be? Well, the qubit state is ψ = 0 = α0 + β1, where α = 1 and β = 0. Measurement will deliver either the state 0 with probability |α|² = 1 (100% certainty), or else the state 1 with probability |β|² = 0 (0% impossibility). So far, so perfectly common sensible...

Now, suppose we pass the qubit through a Hadamard gate before making the measurement. The diagram below shows this new process:

The output of the H gate prior to measurement is ψ = α0 + β1, where α = β = 1/√2; so we have |α|² = |β|² = ½. In other words, the measurement is equally likely to deliver either 0 or 1; the probability of each is 50%. But regardless of which outcome is observed, the state of the qubit after the measurement is just that observed basis state; the original superposition of equal quantities 0 and 1 has been obliterated by the measurement operation.

Review

More than one reader still finds too much unfamiliar notation in my little introductory series, so here's a quick redux of the story so far, without all the matrices and Greek letters...

Qubits without Greek

A single qubit can be represented as an ordered pair of numbers (a, b), where |a|² + |b|² = 1. In this scheme, the pair (1, 0) represents the classical logical 0, while (0, 1) represents classical 1:
(1, 0) = 0
(0, 1) = 1
Similarly, an entangled pair of qubits can be represented as an ordered sequence (a, b, c, d), where |a|² + |b|² + |c|² + |d|² = 1, and the four particular values (1, 0, 0, 0), (0, 1, 0, 0), (0, 0, 1, 0) and (0, 0, 0, 1) stand respectively for the classical states 00, 01, 10 and 11:
(1, 0, 0, 0) = 00
(0, 1, 0, 0) = 01
(0, 0, 1, 0) = 10
(0, 0, 0, 1) = 11
An entangled triplet is represented as a sequence of eight amplitudes (a, b, c, d, e, f, g, h), where |a|² + |b|² + |c|² + |d|² + |e|² + |f|² + |g|² + |h|² = 1, and the following correspondence holds between basis and classical states:
(1, 0, 0, 0, 0, 0, 0, 0) = 000
(0, 1, 0, 0, 0, 0, 0, 0) = 001
(0, 0, 1, 0, 0, 0, 0, 0) = 010
(0, 0, 0, 1, 0, 0, 0, 0) = 011
(0, 0, 0, 0, 1, 0, 0, 0) = 100
(0, 0, 0, 0, 0, 1, 0, 0) = 101
(0, 0, 0, 0, 0, 0, 1, 0) = 110
(0, 0, 0, 0, 0, 0, 0, 1) = 111
When our quantum computers are big enough to contain n entangled qubits, there will be 2ⁿ coefficients or "amplitudes" a, b, c, ..., and still the sum of all their squares will be 1.

Quantum Gates without Matrices

Like classical logic gates, quantum gates are defined by the operation they perform upon their inputs. In the case of a single qubit gate, we could say the input state (a, b) results in the output (a', b'):
(a, b) → (a', b'),
where of course |a'|² + |b'|² = 1. The single-qubit gates we looked at in part 1 were: firstly the quantum wire I, which transmits the input qubit unaltered:
(a, b) → (a, b)
secondly the quantum inverter or NOT gate X, which swaps the two amplitudes of its single-qubit input, and so in particular, converts classical 0 to 1 and vice-versa:
(a, b) → (b. a)

(1, 0) → (0, 1) = 01
(0, 1) → (1, 0) = 10
and lastly, for a bit of quantum exclusivity, the Hadamard gate H, which can combine pure basis states:
(a, b) → ((a+b)/√2, (a-b)/√2)
You might find this last operation written without the √2 scale factors, particularly in multi-step quantum computations, when it is common to roll up such adjustments into a single normalization following the final step of the calculation:
(a, b) → (a+b, a-b)
The only multiple-qubit gate we've seen so far is the controlled-NOT or cNOT gate, which swaps the last two amplitudes of its entangled input qubit pair:
(a, b, c, d) → (a, b, d, c)
By explicitly tracing through the details of the four transitions, we found that this twist corresponded to an inversion of the second qubit, if and only if the first qubit was 1:
(1, 0, 0, 0) → (1, 0, 0, 0) = 0000;
(0, 1, 0, 0) → (0, 1, 0, 0) = 0101;
(0, 0, 1, 0) → (0, 0, 0, 1) = 1011;
(0, 0, 0, 1) → (0, 0, 1, 0) = 1110.
Measurement

Finally, in the first half of this article, we have just covered the question of getting results out of the qubit complex. When you perform a measurement in the computational basis, the single qubit (a, b) will deliver a result of either (1, 0) = 0, with probability |a|², or else (0, 1) = 1, with probability |b|². The qubit will also adopt that measured state, from the point of the measurement onwards; having collapsed into probabilities, there now remains no trace of the original state amplitudes (a, b).

To take a numerical example, the (unknowable) initial state of the qubit might be (a, b) = (+0.8, -0.6). Now suppose a measurement is performed on this qubit. The outcome will be either 0, with a probability of |a|² = 0.8² = 64%, or else 1, with a probability of |b|² = 0.6² = 36%. Notice that the two outcomes have probabilities adding up to 100%, and that between them, they exhaust all the possibilities.

A similar measurement upon a qubit pair in the state (a, b, c, d) will yield a result of (1, 0, 0, 0), i.e. 00, with probability |a|²; alternatively, a result of (0, 1, 0, 0) = 01, with probability |b|²; and so on.

Next time: Superdense Coding.