Quantum Circuit

Circuit model for classical computation

• A universal computation model, equivalent to Turing machine

• A circuit consists of:

  • Wires: represent bits

  • Gates: represent logical operations on bits

• Universal gate sets:

  • AND, OR, NOT and COPY (FANOUT)

  • Can construct

    • any Boolean function $\{0, 1\}^n \to \{0, 1\}^m$

    • any decision problem $\{0, 1\}^n \to \{0, 1\}$

• Universal gate sets is not unique

  • only NAND and COPY (FANOUT) gates

• Circuit size: number of elementary gates ~ circuit width $\times$ circuit depth

• Usually, problem considered to be efficiently solvable if circuit size polynomial to input size

Circuit model for quantum computation

• Use a set of universal gates to implement arbitrary desired function $f: \{0, 1\}^n \to \{0, 1\}^m$

• Construct unitary $U$ such that $U|x\rangle = |f(x)\rangle$ $(\forall x \in \{0, 1\}^n)$

  • Unfortunately, usually such unitary does not exist (because $f$ is usually not reversible)

• Quantum computer unable to perform simplest computation?

  • Solution: use ancilla register to keep reversibility $U|x\rangle|y\rangle = |x\rangle|f(x) \oplus y\rangle$

• Similarly, for 1-bit addition $f(x, y) = x \oplus y$

  • $U|x\rangle|y\rangle|z\rangle = |x\rangle|y\rangle|x \oplus y \oplus z\rangle$

• Fix all initial qubit states to $|0\rangle$, all measurement to be computational basis

  • Other fixed initial states can be absorbed into unitary

  • If algorithm accepts unknown input quantum states, we can initialize first few qubits as input state, other ancilla qubits in $|0\rangle$

Commonly used elementary gates

• Single-qubit gate

  • Pauli gates: $X, Y, Z$

  • Hadamard gate: $H$

  • Phase gate: $S = \begin{bmatrix}1 & 0 \\ 0 & i\end{bmatrix}$

  • $\pi/8$ gate: $T = \begin{bmatrix}1 & 0 \\ 0 & e^{i\pi/4}\end{bmatrix}$

• Simple identities

  • $H X H = Z, H Z H = X$

  • $H^2 = I, S^2 = Z, T^2 = S$

• Single-qubit rotation

  • General rotation around unit vector $\vec{n} = [n_x, n_y, n_z]$

  • Define $\sigma_n = n_x \sigma_x + n_y \sigma_y + n_z \sigma_z$ satisfying $\sigma_n^2 = I$

    $$R(\vec{n}, \theta) = e^{-i \theta \sigma_n / 2} = I \cos\frac{\theta}{2} - i \sigma_n \sin\frac{\theta}{2}$$

• All single-qubit gates can be expressed as some rotation (up to global phase) E.g.

  $$H = R\left(\frac{\hat{x}+\hat{z}}{\sqrt{2}}, \pi\right)e^{i\pi/2}$$

• Two-qubit gate

  • controlled-not (CNOT): flip target if control is $\ket{1}$

    $$\ket{00} \to \ket{00}, \quad \ket{01} \to \ket{01}, \quad \ket{10} \to \ket{11}, \quad \ket{11} \to \ket{10}$$

    $$CNOT = \begin{bmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0\end{bmatrix}$$

    

  • controlled phase flip (CPF) or controlled-Z (CZ)

    $$\ket{00} \to \ket{00}, \quad \ket{01} \to \ket{01}, \quad \ket{10} \to \ket{10}, \quad \ket{11} \to -\ket{11}$$

    $$CZ = \begin{bmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1\end{bmatrix}$$

    

  • Simple circuit identities

    

  • SWAP gate

    $$\ket{00} \to \ket{00}, \quad \ket{01} \to \ket{10}, \quad \ket{10} \to \ket{01}, \quad \ket{11} \to \ket{11}$$

    $$SWAP = \begin{bmatrix}1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}$$

    

• multi-qubit gate

  • $n$-qubit Toffoli gate ($C^{n-1}$-NOT)

    

  • Fredkin gate (controlled SWAP, CSWAP)

    

Universality

• Consider $n$ qubits and a set $S$ of unitary gates acting on them.

• $S$ is universal if $\forall V \in U(2^n)$ and $\forall \delta > 0$, there exists finite gate sequence $\{g_i \in S\}(i=1,...,m)$ and global phase $\phi$ such that

  $$\| V - e^{i\phi} g_m g_{m-1} ... g_1 \| \le \delta$$

  Any unitary $V$ can be approximated to any accuracy by universal gate set.

• Examples

  • All single-qubit gates and CNOT gates between all pairs of qubits

  • H, S, T and CNOT is universal

• Solovay-Kitaev theorem

  • Poly-log $O(\log^c(1/\delta))$ gates from a discrete universal gate set is sufficient to approximate any unitary gates under constant dimension to accuracy $\epsilon>0$.

  • Efficiently approximation in terms of accuracy

• There exist $n$-qubit gates that cannot be decomposed into a polynomial number of elementary gates.

  • Inefficient in terms of number of qubits

• Some commonly used decompositions

  • Single-qubit gate

    $$U = e^{i\alpha} R_z(\beta) R_y(\gamma) R_z(\delta)$$

    where $\alpha, \beta, \gamma, \delta \in \mathbb{R}$, $e^{i\alpha}$ is irrelevant global phase

    • Decompose general rotation into rotations around two axes
    • Similar to Euler angles in 3D space

  • Purpose?

    • Continuous rotation into more continuous rotations

    • Convenient for current experiment without QEC

      • Adjust rotation angle by laser or microwave strength or duration, no additional experimental difficulty

      • Much more efficient than long sequence of $H, S, T$ gates

    • For decomposing controlled single-qubit gate into single-qubit and CNOT

      

      

  • Multi-controlled single-qubit gate

    

    • Toffoli gate

      

    • Construct multi-controlled single-qubit gate

      

• Quantum computer can efficiently simulate classical computer

  • NAND and COPY are universal for classical computation

  • Quantum computer can simulate NAND and COPY (in reversible way)

  • So any function that can be efficiently computed by classical computer can also be efficiently computed by quantum computer

  • Algorithm: Given efficiently computable classical function $f$ as input, generate quantum circuit for unitary $U_f$ using polynomial number of elementary gates as output, s.t. $U_f|x\rangle|y\rangle = |x\rangle|f(x) \oplus y\rangle$

    1. Construct polynomial classical circuit for $f$ using NAND and COPY
    2. Map classical NAND and COPY to quantum version with help of ancilla qubits
    3. Reverse intermediate steps to disentangle ancilla qubits
    4. Decompose quantum NAND and COPY into constant number of elementary gates

    Quantum computer at least as powerful as classical computer, but large constant overhead

    Examples:

    

    

    

Measurement

• Quantum state destroyed after measurement, so to reuse qubits, need to reset them to $|0\rangle$

• Example: stabilizer measurement for QEC

  • $\ket{\phi^+}$ is simultaneous eigenstate of $X_1 X_2$ and $Z_1 Z_2$ with eigenvalue +1

  • How to verify this in circuit (without destroying state)?

    

Quantum Algorithm

• Universal quantum computer at least as efficient as classical computer

• Some problems, like Grover’s algorithm, proved quadratic speedup

• Some problems, like Shor’s algorithm, exponential speedup compared with best-known classical algorithm (but do not know if better classical algorithm exists)

• Use unitary gate $U$ to implement arbitrary desired function $f: \{0, 1\}^n \to \{0, 1\}^m$

  $$U|x\rangle|y\rangle = |x\rangle|f(x) \oplus y\rangle$$

  $$U|x\rangle|0\rangle = |x\rangle|f(x)\rangle$$

  Suppose qubits in superposition states

  $$\ket{\psi} = \sum_i \psi_i \ket{i}$$

  Run same circuit for one time

  $$U \ket{\psi} = \sum_i \psi_i U|i\rangle$$

  Effectively apply $U$ to all basis simultaneously

• But only one measurement outcome

  • Generally require quantum state tomography: exponential cost, no speedup

  • For certain problems, we can find clever way to increase probability of getting desired outcome through interference between different states

  • So intuitively many quantum algorithms shall look like

    

Quantum parallelism

• Deutsch Algorithm

  • Problem: Given $f: \{0, 1\} \to \{0, 1\}$. Want to decide if $f(0) = f(1)$ or not.

  • Motivation

    • Although input and output are simple, evaluation process can be complicated.

    • Example: $f(n)$ can be the number of solutions modulo two to the equation $J_n(x) = \sin^{n+1}(x)$ between $x \in [10, 20]$.

    • Want to reduce the number of calls as much as possible.

  • Classical Approach

    • Evaluate $f(0)$ and $f(1)$ and compare them.

    • Requires two function calls in terms of query complexity.

  • Quantum Approach

    • Only one function call is needed.

    • Construct unitary $U_f$ for the reversible version of function $f$.

      

    • Algorithm

      

    • Observation

      $$U_f \ket{x}\ket{-} = \ket{x}\frac{|f(x)\rangle - |1 \oplus f(x)\rangle}{\sqrt{2}} = (-1)^{f(x)} \ket{x} \ket{-}$$

      $$U_f \ket{+}\ket{-} = \frac{(-1)^{f(0)} \ket{0} + (-1)^{f(1)} \ket{1}}{\sqrt{2}} \ket{-}$$

    • Finally observe first qubit can determine if $f(0) = f(1)$ or not.

• Deutsch-Jozsa algorithm

  • Generalize to $n$ qubits.

  • Given $f: \{0, 1\}^n \to \{0, 1\}$, want to decide if $f$ is constant or balanced (half 0, half 1).

  • Classical: in worst case, need $2^{n-1} + 1$ function calls.

  • Quantum: only one function call is needed.

    

  • Input state: equal superposition of all computational basis states.

    $$H^{\otimes n} |0\rangle^{\otimes n} = \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} |x\rangle$$

  • After function call

    $$U_f \left( \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} |x\rangle \right) |-\rangle = \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} (-1)^{f(x)} |x\rangle |-\rangle$$

  • Finally observe first $n$ qubits can determine if $f$ is constant or balanced.

    • If constant, always measure $|0\rangle^{\otimes n}$

    • If balanced, never measure $|0\rangle^{\otimes n}$ (consider projecting on the equal superposition state above)

  • Remark: if probabilistic classical algorithm is allowed, $\log(1/\epsilon)$ calls is sufficient, independent of $n$. Then quantum approach's improvement for average performance is not significant.

• Bernstein-Vazirani algorithm

  • Given $f: \{0, 1\}^n \to \{0, 1\}$ with promise that there exists a hidden string $s \in \{0, 1\}^n$ such that $f(x) = s \cdot x = s_1 x_1 \oplus s_2 x_2 \oplus ... \oplus s_n x_n$ (mod 2 inner product). Want to find $s$.

  • Classical: impossible to get $s$ using less than $n$ function calls.

  • Quantum: only one function call is needed. (Exactly same circuit as Deutsch-Jozsa)

  • After function call

    $$U_f \left( \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} |x\rangle \right) |-\rangle = \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} (-1)^{s \cdot x} |x\rangle |-\rangle$$

  • Finally observe first $n$ qubits can determine $s$.

    $$H^{\otimes n} \left( \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} (-1)^{s \cdot x} |x\rangle \right) = H^{\otimes n} \left(H^{\otimes n} |s\rangle \right) = |s\rangle$$

Grover's search algorithm

• Search problem

  • Structured search: binary search in sorted list, $O(\log N)$

  • Unstructured search: search in unsorted list, $O(N)$

  • Above examples: data are stored in database: check if stored elements are target

  • Variant: elements not stored, but computed by function.

  • Task: Given $f_\omega: \{0, 1\}^n \to \{0, 1\}$ satisfying

    $$f_\omega(x) = \begin{cases}1 & x = \omega \\ 0 & x \ne \omega\end{cases}$$

    Want to find $\omega$, which is called solution to this search problem.

  • It's unstructured search, classical complexity: $O(N), N = 2^n$.

  • Again, unitary gate $U_{f_\omega}$ as oracle.

    $$U_{f_\omega} |x\rangle |-\rangle = (-1)^{f_\omega(x)} |x\rangle |-\rangle$$

    Omit ancilla qubit for simplicity

    $$U_\omega |x\rangle = (-1)^{f_\omega(x)} |x\rangle$$

  • Again, initialize equal superposition state

    $$|S\rangle = \frac{1}{\sqrt{2^n}} \sum_{x = 0}^{2^n - 1} |x\rangle$$

    and apply the oracle, and measure in computational basis

    

    where $U_S$ is defined to add phase $\pi$ for $|S\rangle$, and leave orthogonal states unchanged.

  • How does Grover's algorithm work?

    • Only consider 2-dim subspace spanned by $|\omega\rangle$ and

      $$|\sigma\rangle = \frac{1}{\sqrt{2^n-1}} \sum_{x \ne \omega} |x\rangle$$

      initial state is

      $$|S\rangle = \frac{1}{\sqrt{2^n}} |\omega\rangle + \sqrt{1 - \frac{1}{2^n}} |\sigma\rangle$$

      

    • $U_\omega$ is reflection about $|\sigma\rangle$ axis, and $U_S$ is reflection about $|S\rangle$ axis.

      $$\sin\theta = \frac{1}{\sqrt{2^n}}$$

      Need $T$ iterations for final state close to $|\omega\rangle$ axis

      $$(2T+1)\theta \approx \pi / 2, \quad T \approx \frac{\pi}{4} \sqrt{2^n} - \frac{1}{2} = O(\sqrt{N})$$

    • Choose $T$ to be closest integer, the prob. to get incorrect result is $O(\theta^2)$, exponentially small.

    • Quadratic speedup for brutal-force search algorithm of NP problems, although still exponential.

Shor's factoring algorithm

• RSA crypto system

  • Security relies on difficulty to compute private key from public key.

    • Choose two large random prime numbers $p, q$.

      $$n = pq, \quad \varphi(n) = (p-1)(q-1)$$

    • Choose small integer $e>1$ s.t.

      $$\gcd(e, \varphi(n)) = 1$$

    • Calculate multiplicative inverse of $e$ module $\varphi(n)$

      $$ed \equiv 1 \mod \varphi(n)$$

    • Public key: $(n, e)$, private key: $(n, d)$.

    • Encryption: given plaintext $m \in \{0, 1, ..., n-1\}$

      $$c \equiv m^e \mod n$$

    • Decryption: given cipher text $c \in \{0, 1, ..., n-1\}$

      $$m \equiv c^d \mod n$$

    • Factor $n$-bit large integer by brutal-force: $O(2^{n/2})$ using best-known classical algorithm.

  • Factoring can be reduced to order-finding problem.

    • Randomly choose $1 < a < L$. If $\gcd(a, L) \ne 1$, it is a factor of $L$.

    • If $\gcd(a, L) = 1$, find smallest $r$ s.t.

      $$a^r \equiv 1 \mod L$$

      If $r$ is even and $a^{r/2} \not\equiv -1 \mod L$ (w.p. $O(1)$), then

      $$\gcd(a^{r/2} - 1, L)$$

      is a non-trivial factor of $L$.

  • Remaining problem is to find order of $a$ modulo $L$.

    • Define function

      $$f(x) = a^x \mod L$$

      which is periodic with period $r$.

• Quantum algorithm for period-finding

  • Integer power $f(x)$ in $\log_2 x$ time by classical computer, which gives us efficient circuit for $U_f$.

  • $n$ qubit input $N \equiv 2^n > r$, and $m$ qubit output $2^m > L$.

    $$U_f \left(\frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle_A |0\cdots0\rangle_B \right) = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle_A |f(x)\rangle_B$$

  • Measure $B$, conditioned on outcome $f(x_0)$, $A$ collapses to

    $$\frac{1}{\sqrt{M}} \sum_{j=0}^{M-1} |x_0 + jr\rangle_A, \quad M = \lfloor (N - x_0 - 1)/r \rfloor + 1$$

    where $x_0$ is uniformly distributed in $\{0, 1, ..., r-1\}$.

    but how to extract $r$?

  • Quantum Fourier Transform (QFT)

    • QFT

      $$\sum_x f(x) |x\rangle \to \sum_y g(y) |y\rangle = \frac{1}{\sqrt{N}} \sum_y \left( \sum_x f(x) e^{2\pi i xy / N} \right) |y\rangle$$

      That is

      $$|x\rangle \to |\phi_x \rangle \equiv \frac{1}{\sqrt{N}} \sum_y e^{2\pi i xy / N} |y\rangle$$

      $\phi_x$ are orthonormal basis.

    • Circuit

      

      Gate complexity: $O(n^2) = O(\log^2 N)$ due to constant # of gates for each controlled rotation.

  • Apply QFT to $A$ (after first measurement)

    $$\frac{1}{\sqrt{M}} \sum_{j=0}^{M-1} |x_0 + jr\rangle_A \to \frac{1}{\sqrt{MN}} \sum_{y=0}^{N-1} \left( \sum_{j=0}^{M-1} e^{2\pi i (x_0 + jr) y / N} \right) |y\rangle_A$$

  • If $N$ is multiple of $r$, then $M = N/r$.

    $$= \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1} e^{2\pi i x_0 k / r} |k N / r\rangle_A$$

    Measuring $A$ gives $y = k N / r$ with equal probability for $k = 0, 1, ..., r-1$. Repeat few times and take gcd to get $N/r$.

  • If $N$ is not multiple of $r$, the probability to get $y$ is

    $$\text{Prob}(y) = \frac{1}{MN} \left| \sum_{j=0}^{M-1} e^{2\pi i (x_0 + jr) y / N} \right|^2 = \frac{1}{MN} \frac{\sin^2(\pi M r y / N)}{\sin^2(\pi r y / N)}$$

    which is sharply peaked at $y$ satisfying $r y / N$ is close to integer.

Quantum Error Correction

• Above algorithms assume perfect state preparation, gates and measurements.

• In practice

  • Currently, possible, but very challenging, to achieve error rate below 0.1%.

  • Not sufficient for applications like Shor's algorithm on 1000 qubits.

  • One exception is topological quantum computer, but lacks experimental progress.

• Therefore it's necessary to perform QEC.

  • Assuming perfect operations, how to deal with existing errors?

  • Assuming faulty operations, is QEC still possible?

• Encode small number of logical qubits into large number of physical qubits.

• Will error correction operations introduce more errors?

  • Threshold theorem:

    There exists a threshold $p_{th}>0$ s.t., if error for elementary components are below $p_{th}$, then arbitrarily large quantum computation can be achieved at any desired accuracy by concatenating QEC codes.

  • Best-known threshold: about 1% for surface code.

  • E.g. factor 1000-bit integer

    • 2000 logical qubits with error rate below $10^{-9}$.

    • or $10^6$ physical qubits with error rate below $10^{-4}$.

Classical error correction

• Repetition Code: Encode each bit multiple times to reduce error probability.

  • Suppose each bit has a small probability $p \ll 1$ to be flipped during storage.

  • Assume independent error on different bits.

  • Encode into $00\cdots0$ and $11\cdots1$ with length $2t + 1$.

    • Error rate suppressed to $O(p^{t+1})$.

    • Need $t + 1$ bit flipped to change majority vote.

• Sources of Errors:

  • Imperfect gate operation during computation.

  • Interaction with environment during storage.

• Modern Classical Computers:

  • Error rates are extremely low.

  • Estimated to be 1 bit error in 4GB data in 24 hours at sea level near Earth's surface.

  • Usually not considered for daily usage.

  • If error occurs, just run the program again.

• Quantum Computers:

  • Error correction is more important due to higher error rates.

  • Potential difficulties in generalizing classical error correction to quantum systems:

    • No-cloning theorem: Unable to copy unknown quantum states, making it challenging to encode repetition codes.

    • Measurement destroys quantum states: Decoding errors and correcting them without destroying the quantum state is non-trivial.

    • Continuous quantum errors: Unlike classical errors which are discrete, quantum errors are continuous. Correcting continuous errors without introducing new inaccuracies is a significant challenge.

• Importance of independent error assumption:

  • In classical repetition codes, if all bits flip together at an error rate $p$, correction becomes impossible.

  • Similar issues arise in quantum error correction.

QEC code

3-qubit code

• A toy model to show important properties of QEC

• Use 2-dim subspace of 3 physical qubits to encode 1 logical qubit.

  $$|0\rangle_L = |000\rangle, \quad |1\rangle_L = |111\rangle$$

  • A logical qubit $|\psi\rangle_L = \alpha |0\rangle_L + \beta |1\rangle_L$ encoded as

    $$|\psi\rangle_L = \alpha |000\rangle + \beta |111\rangle$$

    

  • First problem solved: Although unable to copy unknown state, we can copy in computational basis.

• How does this code work

  • Suppose bit-flip error $X$ occurs on qubit 1.

    $$X_1 |\psi\rangle_L = \alpha |100\rangle + \beta |011\rangle$$

  • Subspace for error $X_1$ spanned by $\{|100\rangle, |011\rangle\}$ is orthogonal to logical space spanned by $\{|000\rangle, |111\rangle\}$.

  • Similarly, subspace spanned by $X_2$ and $X_3$ are also orthogonal to each other.

  • In principle, $I$, $X_1$, $X_2$, $X_3$ can be distinguished by projective measurement.

• How to detect error?

  • Do not measure in computational basis and make majority vote (destroys quantum state).

  • Mathematically, want projective measurement for $P_I$, $P_{X_1}$, $P_{X_2}$, $P_{X_3}$

    • They are simultaneous eigenstates of $Z_1 Z_2$ and $Z_2 Z_3$ with different eigenvalues.

      Error	$Z_1 Z_2$	$Z_2 Z_3$
      $I$	+1	+1
      $X_1$	-1	+1
      $X_2$	-1	-1
      $X_3$	+1	-1

    • Therefore if we measure $Z_1 Z_2$ and $Z_2 Z_3$ (non-demolition), four possible outcomes correspond to four possible subspaces.

  • Further apply corresponding $X_i$ to correct error.

  • Second problem solved: just measure subspaces without revealing information about logical qubit.

• But actual errors are continuous

  • E.g. small rotation $R_X^1(\theta)$ on qubit 1

    $$R_X^1(\theta) |\psi\rangle_L = \cos\frac{\theta}{2} \left( \alpha |000\rangle + \beta |111\rangle \right) - i \sin\frac{\theta}{2} \left( \alpha |100\rangle + \beta |011\rangle \right)$$

  • Just regard it as discrete $I$, $X_1$, $X_2$, $X_3$ errors and perform stabilizer measurement.

    • w.p. $\cos^2(\theta/2)$, project to logical space, no error.

    • w.p. $\sin^2(\theta/2)$, project to subspace for $X_1$ error, then correct it.

  • Third problem solved: syndrome measurement projects continuous errors into discrete ones, which in principle can be corrected perfectly.

• We want them to have distinct error syndromes

  • Two-qubit error $X_1 X_3$ has same syndrome as $X_2$.

  • If we correct it by applying $X_2$, it becomes logical error $X_L$.

  • Similar situation also occurs for classical 3-bit repetition code: unable to correct two-bit errors.

  • Assumptions about errors: rare and independent on different qubits, then $P(X_i X_j) \approx p^2 \ll P(X_i) \approx p$.

• However 3-qubit code cannot correct all possible single-qubit errors

  • E.g. phase-flip error $Z_1$ on qubit 1

    $$Z_1 |\psi\rangle_L = \alpha |000\rangle - \beta |111\rangle$$

  • Subspace spanned by $\{ |000\rangle, |111\rangle \}$ is invariant under $Z_i$.

  • Therefore cannot distinguish $I$, $Z_1$, $Z_2$, $Z_3$ by syndrome measurement.

• $H$ changes $X$ and $Z$ bases

  • $\{|+++\rangle, |---\rangle\}$ stabilized by $X_1 X_2$ and $X_2 X_3$ can correct single $Z$ error, but not $X$ error.

9-qubit Shor code

• Concatenation of these two codes to correct both $X$ and $Z$ errors

  $$|0\rangle_L = \frac{|000\rangle + |111\rangle}{\sqrt{2}} \otimes \frac{|000\rangle + |111\rangle}{\sqrt{2}} \otimes \frac{|000\rangle + |111\rangle}{\sqrt{2}}$$

  $$|1\rangle_L = \frac{|000\rangle - |111\rangle}{\sqrt{2}} \otimes \frac{|000\rangle - |111\rangle}{\sqrt{2}} \otimes \frac{|000\rangle - |111\rangle}{\sqrt{2}}$$

• Encode 1 logical qubit into 9 physical qubits, need 8 independent stabilizers

  • Low level: $Z_1 Z_2$, $Z_2 Z_3$, $Z_4 Z_5$, $Z_5 Z_6$, $Z_7 Z_8$, $Z_8 Z_9$ to correct $X$ errors

  • High level: $(X_1 X_2 X_3)(X_4 X_5 X_6)$, $(X_4 X_5 X_6)(X_7 X_8 X_9)$ to correct $Z$ errors

• No need to distinguish $Z_1, Z_2, Z_3$, same error syndrome corrected by same recovery operation, e.g. $Z_1$ or $Z_1Z_2Z_3$.

• Single $Y$ error has unique syndrome. Or regard $Y_i = i X_i Z_i$ and correct separately.

• Project continuous errors into discrete $I, X, Y, Z$, then arbitrary $\alpha I + \beta X + \gamma Y + \delta Z$ error on one qubit can be corrected.

• Alternative understanding: Shor code is distance-3, thus require 3-qubit Pauli operation to turn one logical state to another. In logical space, there are no overlap between possible states after one single-qubit error.

• In general, QEC code with distance $d=2t+1$ can correct arbitrary $t$-qubit errors.

• Encode $k$ logical qubits into $n$ physical qubits, denoted as $[[n, k, d]]$ code. Shor is $[[9, 1, 3]]$ code.

Commonly used QEC codes

• $[[5, 1, 3]]$ code: smallest code to correct single-qubit errors.

• $[[7, 1, 3]]$ Steane code: Separated $X$ and $Z$ stabilizers.

• $[[25, 1, 9]]$ code by concatenating two $[[5, 1, 3]]$ codes (replace each physical qubit of outer code by inner code) to correct up to 4-qubit errors.

• In general $[[n_1n_2, 1, d_1 d_2]]$ code by concatenating $[[n_1, 1, d_1]]$ and $[[n_2, 1, d_2]]$ codes.

Fault-tolerant Quantum Computation

• Logical qubits encode into block of physical qubits.

• State preparation, logical gates, measurement directly on encoded blocks.

• Insert QEC operations before and after each logical gate (prevent error accumulation and propagation).

• Fault-tolerant: For $[[n, 1, 2t+1]]$ code, if each elementary (physical) operation has error rate below $p \ll 1$, then a logical operation is fault-tolerant if any $O(p^t)$ events can cause at most $t$ errors in each block for logical qubit.

  • The main idea is putting all FT operations (preparation, gate, measurement, QEC) together, any events with $\le t$ failures do not lead to error in final output, thus suppressing error rate to $O(p^{t+1})$.

Example: fault-tolerant measurement

• Start from non-demolition measurement

  

• Measure multi-qubit Pauli operator, not FT.

  

  • $X$ error propagates to all physical qubits.

  • $Z$ error leads to incorrect outcome.

• To prevent error propagates to multiple physical qubits, use multiple ancilla in GHZ states. Still not fully FT.

  

  • If error occurs in preparation step, it still propagates.

• Solution: add verification stage between preparation and non-demolition measurement stages.

  

  • Repeat preparation-verification until no error detected.

  • Single-failure events lead to at most one error on physical qubits, but possibly wrong measurement outcome.

  • Denote this whole process as FTsubMeas (sub-measurement)

• Remaining problem: possibly incorrect outcome.

  • For non-demolition measurement, ideally logical state projected to eigenstate after measurement.

  • Measure for multiple times and make majority vote.

  • Insert fault-tolerant QEC between sub-measurements to correct single-qubit physical errors. For distance-$d$ code, apply $d$ FTsubMeas subroutines.

Example: fault-tolerant QEC

• FT measurement of error syndromes

  • We only care about "current" error syndrome.

    

  • Repeated until last two rounds give same error syndrome.

• FT correction

  • Same as FT single-qubit gate.

  • By definition, tensor product of single-qubit gates on physical qubits is directly fault-tolerant

  • For example, for Steane code

    $$Z_L = Z_1 \cdots Z_7, \quad X_L = X_1 \cdots X_7$$

    $$H_L = H_1 \cdots H_7, \quad S_L = S_1^\dagger \cdots S_7^\dagger$$

  • We can verify

    $$H_LZ_LH_L = X_L, \quad H_L X_L H_L = Z_L$$

    $$S_L Z_L S_L^\dagger = Z_L, \quad S_L X_L S_L^\dagger = Y_L$$

  • We say that these gates are transversal.

Example: fault-tolerant two-qubit gate

• Generalize to transversal gate for multiple logical qubits: pairwise multi-qubit gates on physical qubits from different logical qubits.

• Transversal logical two-qubit CNOT gate for Steane code.

  $$\text{CNOT}_{abL} = \text{CNOT}_{a_1 b_1} \cdots \text{CNOT}_{a_7 b_7}$$

• We can verify

  $$\text{CNOT}_{abL} X_{aL} \text{CNOT}_{abL} = X_{aL} X_{bL}, \quad \text{CNOT}_{abL} Z_{aL} \text{CNOT}_{abL} = Z_{aL}$$

  $$\text{CNOT}_{abL} X_{bL} \text{CNOT}_{abL} = X_{bL}, \quad \text{CNOT}_{abL} Z_{bL} \text{CNOT}_{abL} = Z_{aL} Z_{bL}$$

Remark

• Not all logical gates can be implemented transversally.

  • Theorem: A transversal gate set cannot be universal.

  • For Steane code, we have transversal gate $H_L$, $S_L$, CNOT$_L$, but not $T_L$. Need a different way to implement.

• Theorem: There exists a threshold $p_{th}$ for fault-tolerant quantum computing. If physical operations all have error rates below $p<p_{th}$, then for any ideal quantum circuit $C$ and any desired accuracy $\epsilon>0$, there exists physical quantum circuit $C'$ to simulate output of $C$ with error rate below $\epsilon$. Overhead of $C'$ is $O(\text{polylog}(|C|/\epsilon))$ where $|C|$ is size of circuit $C$.

  • Implicit assumption that different quantum operations on different qubits can be performed in parallel, or that storage lifetime is infinite.

  • Otherwise, when encoding into higher level, we increase idling time of other physical qubits, during which QEC cannot be performed.

  • Threshold about $p_{th} = 1/c$ with $c$ being number of pairs of positions where two physical errors can lead to logical error.

  • For Steane code $c \sim 10^4$, threshold $p_{th}$ about $10^{-5}\sim 10^{-4}$.

  • To date, best-known threshold is about 1% for surface code.