Quantum information: qubits, gates, circuits and no-cloning

A classical computer manipulates bits with logic gates. A quantum computer manipulates qubits with unitary operations, also called gates, and reads them out by measurement. This lesson builds the circuit model of quantum computation from the physics of earlier lessons. It introduces the standard single- and two-qubit gates, shows that a small set of them is universal, and derives two results that set quantum information apart from classical information: the no-cloning theorem, which forbids copying an unknown quantum state, and quantum teleportation, which transfers one using entanglement and two classical bits.

Single-qubit gates

A single-qubit gate is a \(2 \times 2\) unitary matrix, which up to a global phase is a rotation of the Bloch sphere. The most common have names:

Any single-qubit unitary can be written as \(e^{i\alpha}R_z(\beta)R_y(\gamma)R_z(\delta)\), with \(R_{\hat n}(\theta) = e^{-i\theta\,\hat n\cdot\boldsymbol\sigma/2}\), the Euler-angle decomposition. Physically, gates are applied by driving the qubit, a resonant microwave or laser pulse of controlled duration and phase producing a rotation about an axis in the \(xy\) plane, exactly the Rabi oscillation of PHYS-373 viewed in the rotating frame. A \(\pi\) pulse is an X gate and a \(\pi/2\) pulse, combined with phase shifts, gives the Hadamard.

Two-qubit gates and entanglement

Single-qubit gates cannot create entanglement, since they act on each qubit separately. The standard entangling gate is the controlled-NOT, CNOT, which flips the target qubit when the control is \(|1\rangle\):

Acting on \(|{+}\rangle|0\rangle\) it gives \((|00\rangle + |11\rangle)/\sqrt2\), so a Hadamard followed by a CNOT turns \(|00\rangle\) into a Bell state. Running the circuit in reverse, CNOT then Hadamard, maps the four Bell states to the four computational basis states, which is how Bell states are measured. Other entangling gates include the controlled-Z and the iSWAP, which are more natural on some hardware. Superconducting qubits, for example, implement entangling gates by tuning two qubits into resonance or by driving one at the frequency of the other, and trapped ions by using shared motional modes as a bus.

A set of gates is universal if any unitary on any number of qubits can be approximated by a circuit built from it. The CNOT together with all single-qubit gates is universal exactly, a result of Barenco and colleagues in 1995. For fault tolerance one wants a finite set, and \(\{H, T, \text{CNOT}\}\) is universal in the sense of approximation; the Solovay–Kitaev theorem guarantees that the approximation needs only a number of gates growing polylogarithmically with the required precision.

The no-cloning theorem

Could a machine copy an arbitrary unknown state, turning \(|\psi\rangle|0\rangle\) into \(|\psi\rangle|\psi\rangle\)? In 1982 William Wootters and Wojciech Zurek, and independently Dennis Dieks, proved that it could not. Suppose a unitary \(U\) did this for two states \(|\psi\rangle\) and \(|\phi\rangle\), so that \(U|\psi\rangle|0\rangle = |\psi\rangle|\psi\rangle\) and \(U|\phi\rangle|0\rangle = |\phi\rangle|\phi\rangle\). Taking the inner product of the two equations and using unitarity gives

so \(\langle\phi|\psi\rangle\) is 0 or 1. A cloner can copy a set of mutually orthogonal states, but no two distinct non-orthogonal ones. The argument extends to machines that use ancillas and measurement. The CNOT illustrates it. It copies \(|0\rangle\) and \(|1\rangle\) perfectly, but applied to \(|{+}\rangle|0\rangle\) it produces a Bell state, not \(|{+}\rangle|{+}\rangle\), and each output qubit is in the maximally mixed state, with fidelity only one half with the original. The best possible approximate cloner, found by Vladimir Bužek and Mark Hillery in 1996, reaches a fidelity of 5/6 for each copy of an unknown qubit.

No-cloning is not a technicality. If unknown states could be copied, an eavesdropper could copy the photons in a quantum key distribution system and measure the copies at leisure, and one half of an entangled pair could be copied and used to send signals faster than light. The theorem is the root of both the security of quantum cryptography and the consistency of entanglement with relativity. It also makes quantum error correction harder than classical: errors cannot be fought simply by keeping backup copies.

Teleportation

Although an unknown state cannot be copied, it can be moved. In 1993 Charles Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres and William Wootters, three of them working in Montréal, showed that a shared Bell pair and two classical bits suffice to transfer a qubit state from Alice to Bob. Alice holds qubit 0 in the unknown state \(\alpha|0\rangle + \beta|1\rangle\) and qubit 1, half of the Bell pair \(|\Phi^+\rangle_{12}\); Bob holds qubit 2. Rewriting qubits 0 and 1 in the Bell basis gives the identity

in which the third factor of each term is Bob's qubit. Alice measures her two qubits in the Bell basis. Each of the four results occurs with probability one quarter and leaves Bob's qubit in a state related to \(|\psi\rangle\) by a known Pauli operation, \(1\), \(Z\), \(X\) or \(ZX\). Alice sends the two result bits to Bob, who applies the inverse operation and obtains \(|\psi\rangle\) exactly. Nothing travels faster than light, because Bob's qubit is useless until the classical bits arrive, and no copy is made, because Alice's measurement destroys the original.

Teleportation was first demonstrated with photon polarization in 1997 by Zeilinger's group in Innsbruck and by Francesco De Martini's group in Rome. It has since been performed with trapped ions, between atoms in separate laboratories, and over 1,400 km from the Micius satellite to the ground in 2017. In quantum networks it moves qubits between processors, and in some error-correction schemes gates themselves are applied by teleportation.

import cmath, math, random

# A tiny statevector simulator. Qubit 0 is the leftmost bit of the basis label.
s2 = 1 / math.sqrt(2)
H = [[s2, s2], [s2, -s2]]; X = [[0, 1], [1, 0]]; Z = [[1, 0], [0, -1]]; I = [[1, 0], [0, 1]]
def gate1(psi, U, q, n):
    out = [0j] * len(psi)
    for idx, amp in enumerate(psi):
        if amp == 0: continue
        bit = (idx >> (n - 1 - q)) & 1
        for nb in (0, 1):
            j = idx ^ ((bit ^ nb) << (n - 1 - q))
            out[j] += U[nb][bit] * amp
    return out
def cnot(psi, c, t, n):
    out = psi[:]
    for idx in range(len(psi)):
        if (idx >> (n - 1 - c)) & 1:
            out[idx ^ (1 << (n - 1 - t))] = psi[idx]
    return out
def show(psi, n):
    return " + ".join(f"({a.real:+.3f}{a.imag:+.3f}i)|{i:0{n}b}>" for i, a in enumerate(psi) if abs(a) > 1e-9)
def measure(psi, q, n, rnd):
    p1 = sum(abs(a) ** 2 for i, a in enumerate(psi) if (i >> (n - 1 - q)) & 1)
    m = 1 if rnd.random() < p1 else 0
    keep = [a if ((i >> (n - 1 - q)) & 1) == m else 0j for i, a in enumerate(psi)]
    nrm = math.sqrt(sum(abs(a) ** 2 for a in keep)); return m, [a / nrm for a in keep]

# 1. Bell state preparation: H on qubit 0, then CNOT 0 -> 1
psi = [1 + 0j, 0, 0, 0]
psi = cnot(gate1(psi, H, 0, 2), 0, 1, 2)
print("Bell state from |00>:", show(psi, 2))
print()

# 2. Teleportation of a random qubit state from qubit 0 to qubit 2
rnd = random.Random(472)
th, ph = rnd.uniform(0, math.pi), rnd.uniform(0, 2 * math.pi)
a, b = math.cos(th / 2), cmath.exp(1j * ph) * math.sin(th / 2)
print(f"state to teleport: {a.real:+.4f}|0> + ({b.real:+.4f}{b.imag:+.4f}i)|1>")
for trial in range(5):
    psi = [0j] * 8; psi[0] = a; psi[4] = b              # |q0> ⊗ |00>
    psi = cnot(gate1(psi, H, 1, 3), 1, 2, 3)              # Bell pair on qubits 1 and 2
    psi = gate1(cnot(psi, 0, 1, 3), H, 0, 3)              # Alice's Bell measurement circuit
    m0, psi = measure(psi, 0, 3, rnd); m1, psi = measure(psi, 1, 3, rnd)
    if m1: psi = gate1(psi, X, 2, 3)                       # Bob's corrections from the two classical bits
    if m0: psi = gate1(psi, Z, 2, 3)
    base = (m0 << 2) | (m1 << 1)
    out = (psi[base], psi[base | 1])
    fid = abs(a.conjugate() * out[0] + b.conjugate() * out[1]) ** 2
    print(f"  outcome bits {m0}{m1}: Bob's qubit = {out[0].real:+.4f}|0> + ({out[1].real:+.4f}{out[1].imag:+.4f}i)|1>   fidelity {fid:.6f}")
print()

# 3. No cloning: a CNOT copies basis states but not superpositions
def reduced(psi, q):                                     # 2x2 density matrix of qubit q of a 2-qubit state
    bit = lambda i, k: (i >> (1 - k)) & 1
    r = [[0j, 0j], [0j, 0j]]
    for i, x in enumerate(psi):
        for j, y in enumerate(psi):
            if bit(i, 1 - q) == bit(j, 1 - q):           # trace over the other qubit
                r[bit(i, q)][bit(j, q)] += x * y.conjugate()
    return r
for name, inp in (("|0>", [1, 0]), ("|1>", [0, 1]), ("|+>", [s2, s2])):
    psi = cnot([complex(inp[0]), 0j, complex(inp[1]), 0j], 0, 1, 2)    # input ⊗ |0>, then CNOT
    fids = []
    for q in (0, 1):
        r = reduced(psi, q)
        fids.append(sum(complex(inp[i]).conjugate() * r[i][j] * inp[j] for i in range(2) for j in range(2)).real)
    print(f"  copy {name}: output {show(psi, 2):40s} fidelity of each copy = {fids[0]:.3f}, {fids[1]:.3f}")

Bell state from |00>: (+0.707+0.000i)|00> + (+0.707+0.000i)|11>

state to teleport: +0.1811|0> + (+0.9270-0.3283i)|1>
  outcome bits 01: Bob's qubit = +0.1811|0> + (+0.9270-0.3283i)|1>   fidelity 1.000000
  outcome bits 01: Bob's qubit = +0.1811|0> + (+0.9270-0.3283i)|1>   fidelity 1.000000
  outcome bits 00: Bob's qubit = +0.1811|0> + (+0.9270-0.3283i)|1>   fidelity 1.000000
  outcome bits 10: Bob's qubit = +0.1811|0> + (+0.9270-0.3283i)|1>   fidelity 1.000000
  outcome bits 11: Bob's qubit = +0.1811|0> + (+0.9270-0.3283i)|1>   fidelity 1.000000

  copy |0>: output (+1.000+0.000i)|00>                      fidelity of each copy = 1.000, 1.000
  copy |1>: output (+1.000+0.000i)|11>                      fidelity of each copy = 1.000, 1.000
  copy |+>: output (+0.707+0.000i)|00> + (+0.707+0.000i)|11> fidelity of each copy = 0.500, 0.500

The simulator represents an \(n\)-qubit state as a list of \(2^n\) complex amplitudes and applies gates by updating them, the same method used by research simulators on a larger scale. Teleportation succeeds with fidelity 1 for every measurement outcome, and the five runs between them produce all four outcomes, each followed by the appropriate correction. The CNOT copier works for \(|0\rangle\) and \(|1\rangle\) but turns \(|{+}\rangle\) into an entangled state whose parts each have fidelity one half with the original, exactly as the no-cloning theorem requires.

Measurement and the circuit model

A circuit ends with measurements, usually of every qubit in the computational basis, and the output is a string of random bits whose probabilities are \(|\langle x|\psi\rangle|^2\). Running the circuit many times builds up the distribution. This is where the limits of quantum parallelism appear. A register of \(n\) qubits in superposition can hold \(2^n\) amplitudes, and one application of a gate updates all of them, but a measurement returns only \(n\) bits. An algorithm is useful only if interference concentrates the probability on outcomes that answer the question, as lesson 11 shows. Measurements can also occur in the middle of a circuit, with later gates conditioned on the classical results; teleportation is the simplest example. The principle of deferred measurement says that such classically controlled gates can always be replaced by quantum controlled gates and the measurement moved to the end, so mid-circuit measurement adds convenience but no new computational power. In hardware, however, mid-circuit measurement and fast feedback are essential for error correction, where syndromes must be read and acted on while the computation continues.

Information in qubits

How much classical information can a qubit carry? Its state needs two real parameters to specify, but Holevo's theorem of 1973 shows that measurements can extract at most one bit of classical information from one qubit. Entanglement changes the accounting: with a shared Bell pair, sending one qubit can transmit two classical bits, superdense coding (Bennett and Wiesner, 1992), the counterpart of teleportation. The quantum analogue of Shannon's theory of communication, developed by Benjamin Schumacher, Holevo and others in the 1990s, measures quantum information in qubits, with the von Neumann entropy of lesson 7 playing the role of Shannon entropy.