Fault-Tolerant Quantum Technologies ’16

After some weeks’ hiatus, Quanta for Breakfast is back! Today I want to give my thoughts on the Fault-Tolerant Quantum Technologies Workshop that I attended this summer in Benasque, Spain. It was my first time visiting the beautiful town and both the location and the workshop definitely lived up to my expectations.

The conference took place at the Centro de Ciencias de Benasque Pedro Pascual, a facility for hosting workshops and scientific meetings and truly a dream come true for physicists at a conference. There were blackboards everywhere: conference theatre, meeting rooms, corridors, outside blinds… It has all the facilities needed to be a place of scientific work and discussion and there is really no excuse to not talk about physics all day long. The building itself had a very interesting design and was built with sustainability in mind. The Centre was named in honour of the Spanish physicist Pedro Pascual, whose Quantum Mechanics book, co-authored with Alberto Galindo, I thoroughly studied as an undergrad at the Universidad Complutense de Madrid. Benasque itself is charming, full of hikers, incredible scenery and good food. There were some complaints about the time it took to have lunch, but what can I say, it’s a holiday town in Spain, restaurants assume the diners want to relax and enjoy the food 🙂 . However, for the people who couldn’t wait to go back to the blackboards, there was always the option of grabbing some tapas.

The meeting was really fantastic, from the content of the talks to the atmosphere throughout the two weeks. On top of the welcome drinks and conference dinner, there were some great activities organised, such as a couple of group hikes, an ascent to Aneto (the tallest peak in the Pyrenees), canyoning and an AMA Reddit session.


Group hike


On top of all these activities, there was plenty of free time for work and discussion, which is mostly missing in other conferences. This free time combined with the group discussions truly gave us the opportunity to learn new concepts and work together. Speaking for myself, not being an expert in Quantum Error Correction, I came back from the conference having a much better understanding of many concepts, in particular around the concept of cellular automata decoders, which featured in several talks (including a video demonstration by Barbara Terhal, shown in the GIF below). The concept of algorithms using cellular automata in quantum information processes is very powerful, particularly when considering cluster state computations or topological error correction, where the information is stored in global degrees of freedom and can be acted upon with local operations.


Demonstration of a cellular automata decoder


The biggest highlight of this workshop was, for me, the extensive discussion around experiments. There were several talks dedicated to the topic:

Steve Flammia: Comparing Experiments to the Fault Tolerant Threshold

– Hector Bombin: On the effect of correlated noise

James Wooton: A decoding algorithm for proof of principle experiments

Ying Li: Resource cost of fault-tolerant quantum computing in hybrid quantum computers and LOQC

Niel de Beaudrap: NQIT

– Yours truly: Fault-tolerant considerations when designing a linear-optical quantum computer

Hugo Cable: Minimised switching in linear-optical quantum computing

– James Auger: Topological Error Correction with Faulty Components

Joe O’Gorman: Realistic magic state distillation factories

Also, there were some technical discussions on experimental implementations of quantum computers, as well as which codes should be the first to be implemented  in small scale experiments.

We are currently at a very exciting point in the development of quantum computers. Experiments are starting to get large enough that some small codes can be tested on them. Proofs of principle experiments of topological codes have been implemented with superconducting qubits, as well as with photons and ion traps. However, the community is not in agreement on which codes are the most useful and what scope we have to find yet better error correction codes. On top of that, it might be the case that the different constraints of the various physical systems make it impossible for a single code to be optimal for all. Good news is that, now that the Quantum Error Correction and experimental communities are engaging so much with each other, we can expect vast improvements on the performance of small quantum computers thanks to codes tailored to the specific requirements of the physical systems.

Finally, I would like to thank the organisers – Dan Browne, Earl Campbell and Michael Kastoryano – for such a fantastic experience, I look forward to future editions of the workshop!



I don’t want to leave the post without mentioning the game Decodoku, a browser and mobile citizen-science game based on Quantum Error Correction, which was advertised at the conference. It’s presented as a series of puzzles, reminiscent of the popular sudoku, 2048 and Threes, but in which the problems solved mimic the effects of noise on a topological code. Good strategies for solving these puzzles efficiently could potentially become new decoding algorithms, it gives an excellent excuse for the time spent playing 😀 . If you find out you are really good at it, let the developer (James Wooton) know.

Quantum computing and its models

Before reviewing in more detail the most promising experimental realisations of quantum information processors, I think it is useful to recap the basic concepts and most used models of quantum computing. In particular, the models, as the physical realisations mentioned in a previous post use different but equivalent computational models, which need to be understood to comprehend their implementations.

The primary logical units of a quantum computer are quantum bits, or qubits, which are two-level quantum systems that can be used to store and process quantum information. The two levels are usually represented by |0\rangle, |1\rangle, which are known as the computational basis states (in Dirac notation). The main difference between bits and qubits is that the latter can be in a linear combination, usually referred to as superposition, of the two basis states. Hence the most general representation of a qubit is:

| \psi \rangle = \alpha |0\rangle + \beta |1\rangle

where  \alpha and \beta are, in general, complex coefficients. When a qubit is measured in the computational basis, the results 0 or 1 are obtained with probability |\alpha|^2 and |\beta|^2 respectively. As these probabilities must add up to one (|\alpha|^2 + |\beta|^2 = 1), we have a normalisation restriction on the coefficients  \alpha and \beta , that can be geometrically understood as the condition that the qubit’s state has length one. We can take this geometric interpretation a bit further and parametrize the quantum state in spherical coordinates

\psi = \cos \theta |0\rangle +e^{i\phi} \sin \theta|1\rangle,

and understand the qubit as a vector in a sphere of radius one. This sphere is usually referred to as the Bloch sphere, shown in the figure below. Note that in this representation, orthogonal states are diagonally opposed rather than at right angles.


The three cartesian axes of the Bloch sphere correspond to the eigenstates of the Pauli matrices: \sigma_X=\begin{pmatrix}  0 & 1 \\  1 & 0 \end{pmatrix} ,\quad \sigma_Y=\begin{pmatrix}  0 & -i \\  i & 0 \end{pmatrix} ,\quad \sigma_Z=\begin{pmatrix}  1 & 0 \\  0 & -1 \end{pmatrix},

where the matrices are written in the computational basis. The eigenstates of the \sigma_Z operator are the computational basis states {|0\rangle, |1\rangle}, whereas the eigenstates of \sigma_X and \sigma_Y are {|\pm \rangle } and {| \pm i \rangle } respectively.

Single-qubit logical gates can be understood as transformations (rotations and reflections) of the states in the Bloch sphere. The most used single qubit gates are:

•Hadamard gate: H=\frac{1}{\sqrt{2}} \begin{pmatrix}  1 & 1 \\  1 & -1 \end{pmatrix}

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

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

• Rotations with respect to one of the cartesian axes: R_{\sigma_k} (\theta) = \cos \theta I-i\sin \theta \sigma_k     where k \in {X, Y, Z}.

The most commonly used two-qubit gate, controlled-NOT (CNOT), has the same truth table as the classical XOR gate, which flips the target (second) bit when the control (first) bit is in the state 1:

|00\rangle  \rightarrow |00\rangle,\  |01\rangle \rightarrow |01\rangle,\  |10\rangle \rightarrow |11\rangle\  \&\  |11\rangle \rightarrow |10\rangle .

The use of the CNOT gate in conjunction with some of the single qubit gates can produce entangled states, which show correlations with no equivalence in classical computation. For example, the action of a CNOT gate with the Hadamard gate on a pair of computational basis qubits yields:

|00\rangle \xrightarrow{H_1} |+0\rangle =\frac{1}{\sqrt{2}}(|00\rangle +|10\rangle) \xrightarrow{CNOT} \frac{1}{\sqrt{2}}(|00\rangle +|11\rangle)

This state (which is one of the four maximally entangled states referred to as Bell pairs), cannot be written as the product of two single-qubit states.

Other entangling gates such as controlled-Phase (CZ) can be obtained from combinations of CNOT gates with single qubit gates; moreover, any multi-qubit unitary can be achieved in the same way, which makes this set of gates universal. A set of gates can perform universal quantum computation if they are sufficient to approximate any unitary operation to an arbitrary accuracy via a quantum circuit. This universality is crucial as it allows any quantum algorithm to be performed and it ensures the equivalence of different models of quantum computation.

There are various quantum computing models that are universal, such as the circuit model, the measurement-based model, adiabatic model, topological model and quantum walk model. However, in this post, I will only focus on the first three models, as thy are the most relevant to the experimental realisations that show most promise today.

Circuit model

The circuit model is an algorithmic model for quantum computing that closely resembles classical algorithms. Single-qubit and two-qubit operations are performed in sequence on a set of qubits initialized in a fiduciary state, and the results are read at the end as the outcome of single-qubit measurements. The entanglement and interference necessary for the quantum speedup are built up during the computation, and if any ancillary states are used, their state must be erased so that they no longer interfere with the rest of the computation.

The following circuit diagram shows the most common representation of the quantum logic gates presented earlier:


The procedure runs from left to right: preparation, single Hadamard gate, CNOT gates, rotation and phase gates, measurement.

Circuit model key facts

State Space: A quantum circuit operates on a number of qubits (or two-level quantum systems), and therefore its state space is a 2^n -dimensional complex Hilbert space. The computational basis states are defined as product states of the form |x_1,...,x_n\rangle, where x_i = 0, 1.

State Preparation: Any computational basis state |x_1,...,x_n\rangle can be prepared in at most n steps.

Quantum Gates: Gates from a universal family of gates can be applied to any subset of the qubits desired.

Measurements: Measurements in the computational basis can be performed on one or more qubits.

Classical Computation: In principle, it is not necessary for the computation, but it can make certain tasks much easier.

Procedure of the computation: Quantum algorithms are run by applying one-qubit and two-qubit gates to the quantum systems, building up the amount of entanglement until the final measurement in the computational basis gives the result of the computation.

Measurement-based quantum computation 

For a long time, the circuit model was commonly used for quantum computation. Measurement-based quantum computation models are radically different to the circuit model (and have no classical analogue), as the resource for the computation is prepared in advance and “offline”. This strategy has the advantage that if errors occur at the preparation stage, the prepared state can be discarded, and the procedure can be repeated without any loss of information. There are two main approaches for measurement based quantum computing: the generalised teleportation model and the one-way quantum computer model. However, the latter is the most widely used, and therefore we will only look at that model here.

In the one-way model, the entire resource for the computation is supplied at the beginning of the computation, in the form of a highly entangled multi-particle state. This state is usually referred to as cluster state, and it is the same for every computation, although it may vary in size. The information is then processed by carrying a series of adaptive single qubit measurements.

This highly entangled multi-particle state is prepared by applying a pattern of entangling gates to the qubits. A generic cluster state of n particles is not easy to write in any basis, but it can be efficiently described with a graph, where each node of the graph represents a qubit and each bond denotes that the two sites have been connected by an entangling controlled-Z gate (CZ) operation. As the computation will be performed by single qubit measurements, the primary challenge of this computational model is the preparation of this highly-entangled cluster state, which can be technically challenging.

The information processing is done via sequential measurement of the qubits in a particular basis. It is assumed that the correct algorithm is performed if all the measurement outcomes are the +1 eigenstate, however, given the probabilistic nature of quantum mechanics, this is not always the case. We can steer the computation back to its correct subspace by applying Pauli corrections to subsequent measurements. Therefore, measurement results determine the basis of the following measurements on other qubits. Finally, the product of the computation is read out by one last measurement in the computational basis.

In the figure below (copyright 2001 by the APS), we can see an example of a quantum algorithm performed using the MBQC model. We initially start with a rectangular cluster state of 6 × 12 qubits, where qubits are located at the vertices of the grid (grid lines are not shown).  Despite starting with 72 physical qubits, this algorithm is actually performed on only 3 logical qubits, which are shown by the three horizontal yellow arrows. The yellow paths between the logical qubits represent two-qubit gates as explained in the circuit model, and the rest of the single-qubit gates are performed by measuring the qubits in the X-Y plane.


This model of computation has an enormous technical advantage over the classic circuit model, which makes it very appealing to implement quantum computation using certain physical systems. The cluster states can be produced offline and only when the resource is prepared correctly, the computation is performed. For many physical systems, performing entangling gates is the most challenging part of the computation, but if we post-select on the successful preparations of the resource state, this model substantially increases the probability of a successful computation. All that is required then is to be able to perform single qubit gates successfully with high fidelity, which is less technologically demanding for many physical systems such as superconducting qubits, ion traps and linear optics.

MBQC model key facts

State Space: A cluster state computation operates on n\times k physical qubits (or two-level quantum systems) for a quantum algorithm with n logical qubits. Its state space is a 2^{n\times k}-dimensional complex Hilbert space. The computational basis states are defined as product states of the form |x_1, \dots , x_{n\times k}\rangle, where x_i = 0, 1. The graph state representation is usually used.

State Preparation: Before the computation starts a resource state must be prepared. This resource state is a highly entangled multi-particle state (cluster state), which is the same (except for its size) for every computation.

Quantum Gates: An entangling gate is performed on qubits in a product state to build the resource state. Afterwards, only single qubit measurements are needed.

Measurements: Single qubit measurements can be performed in an arbitrary basis. (Or if only measurements of the computational basis can be performed, single qubit rotations must be performed alongside.)

Classical Computation: Classical computation alongside the quantum computations is a key feature of this model, as the basis of the measurements performed sequentially depends on the results of previous measurements.

Procedure of the computation: The entire resource for the quantum computation is supplied at the beginning of the computation. The information is then processed by carrying a series of adaptive single qubit measurements.

Adiabatic model

This model represents a new paradigm for quantum computation that was recently proposed based on quantum adiabatic evolution. Computation in this model is not performed by applying gates or measurements to qubits, but rather the algorithm starts from a disordered state, and it arrives at a solution to the problem by performing what can be understood as a local quantum search. The procedure for the computation is as follows:

•At time t = 0, the quantum mechanical system is described by a Hamiltonian H_E, whose eigenstates are easy to compute.

•The system is slowly transformed to the final Hamiltonian at time t = T, whose ground eigenstates are the solution to the problem that needs to be solved. This process can be described by a time-dependent Hamiltonian

H(t) = A(t)H_E + B(t)H_P .

A(t) and B(t) are slowly varying monotonic functions such that A(0) = 1,\  B(0) = 0 and A(T ) = 0,\  B(T ) = 1. According to the adiabatic theorem, if the evolution is slow enough, i.e. T is long enough, and if there is a gap between the ground state eigenvalue and the rest of the Hamiltonian’s spectrum, the state of the system at time t = T would correspond to the ground state of H_P , thus producing the solution to the problem.

•Measurement of the ground state allows for the extraction of the solution.
This model for quantum computation has been proven to be universal for quantum computation.

Adiabatic model key facts

• State Space: Assuming there are n particles to which the Hamiltonian is applied are two-level systems, the state space is 2^n -dimensional.

• State Preparation: The state is prepared in the ground state of the initial Hamiltonian, which is easy to prepare.

Quantum Gates: Once the state is prepared, no gates per se are applied, but rather, the Hamiltonian is adiabatically changed from the initial to the target Hamiltonian.

Measurements: A single measurement of the state of each quantum particle in the system suffices to read out the solution to the problem, which is encoded in the eigenstate of the final Hamiltonian.

Classical Computation: Classical computation is required to find the appropriate Hamiltonian to encode the problem, to which the system will be adiabatically evolved into.

Procedure of the computation: The computation is performed by slowly (adiabatically) varying the Hamiltonian, from the initial (easy to prepare) to the final, which encodes the problem.