This is a companion site for the short course "Ingredients for universal quantum computation" that I've delivered as part of the V Quantum Information School - Paraty 2015, taking place August 4th-8th, 2015 in Paraty, Rio de Janeiro state, Brazil. Here you can find my slides and links to the papers I mentioned in the lectures.
My name is Ernesto F. Galvão, I'm an associate professor at the Physics Department of Universidade Federal Fluminense (Niterói, Rio de Janeiro state, Brazil).
Lecture slides: lecture 1/3, lecture 2/3, lecture 3/3.
*New*: recorded lectures.
Submit questions online. I'd like to encourage students to submit questions about the course material using this online form. Please try to do it ASAP after the lecture, so that I can comment on the questions in my next lecture. Of course, you're more than welcome to ask me questions in person!
Course: Ingredients for universal quantum computation
Abstract: I will start by reviewing the main ingredients for a universal quantum computer in the circuit model: universal sets of gates, the importance of restricting input states and output measurements, etc. Then I will review the basics of alternative models of quantum computation, such as measurement-based quantum computation and models which use linear optics (e.g. the KLM scheme and Boson Sampling). By mixing and matching the various ingredients, we will identify different combinations which yield interesting regimes in terms of computational power: full universal quantum (or classical) computation, simulable quantum dynamics, or an intermediate or incomparable computational power (e.g. IQP, Boson Sampling, permutational quantum computing, DQC-1). This line of research helps identify what’s essential and what’s accessory for the quantum computational advantage, with practical implications for experimental implementations. I will give special attention to recent experimental progress in specialized linear optical computers to solve the Boson Sampling problem, which I will describe in some detail.
Course outline and references:
1- Universal quantum computation in the circuit model
Basics of circuit model: input, unitaries (and their graphical notation), measurement. Single-qubit gates are rotations of the Bloch sphere. Sketch of proof that the gate-set {H, T, CNOT} is (approximately) universal. Approximating unitaries using the Solovay-Kitaev algorithm [Dawson/Nielsen review paper].
Other universal sets of gates: {Toffoli, H} (actually, any non-basis preserving single-qubit unitary serves the purpose, together with Toffoli - [Shi paper, Aharonov paper with a simpler proof of this]. This gate-set consists of orthogonal matrices, which operating in the computational basis will never result in states with complex coefficients. So it must be possible to quantum-compute efficiently with no need for complex numbers (on "rebits"=qubits with real amplitudes), and this is indeed the case [Rudolph/Grover paper, McKague paper].
The concept of encoded universality (see paper by Bacon et al.). Other (encoded) universal gate-sets:{matchgates, SWAP} (likely discussed in Richard Jozsa's lectures). A single interaction is sufficient: gates from the exchange interaction [ Kempe et al. paper], {generic two-qubit unitary} [see paper by Childs et al.].
Certain unitaries require an exponential number of gates to implement. Complexity class BQP consists of problems solvable by poly(n)-sized circuits (check out this introductory lecture by Scott Aaronson on the main complexity classes relevant to us). The problem with allowing general, global output measurements.
Our first restricted computer: one with gates only from the Clifford group of unitaries. Defining the Pauli and the Clifford group: normalizer of the Pauli group. Efficient simulation using the Heisenberg picture (the Gottesman-Knill theorem - see Gottesman's introductory paper).
Sometimes we can "upgrade" the computational power of a restricted quantum computer. Example: Clifford computer + magic states (Bravyi/Kitaev paper).
2- Restricted models of quantum computation
What's a restricted quantum computer, motivations. Simulability notions (reference to Jozsa course, weak and strong simulations). A general recipe for proving that a restricted model is hard to simulate (using postselection).
Description of some restricted models:
2.1 IQP: commuting quantum computations. Description, hardness proof, possible applications. Relevant papers:
* First Shepherd/Bremner paper, defining IQP.
* Bremner/Jozsa/Shepherd original paper with an argument that exact simulation of IQP would collapse the Polynomial Hierarchy.
* Recent paper by Bremner/Montanaro/Shepherd relating the hardness of simulation with other (supposedly) hard problems. This paper by Fujii and Morimae was the first the make the connection with partition functions of the Ising model.
* Some applications of circuits with diagonal unitaries - paper by Nataka and Murao.
2.2 DQC-1: description of the model, what it's good for, proofs that it's hard to simulate, presence (or absence) of entanglement and other correlations.
* Original paper by Knill, Laflamme (1998)
* For Jones polynomials (Shor, Jordan 2007)
* Small entanglement in this model: Datta, Flammia, Caves 2005
* Application: fidelity decay (David Poulin, Robin Blume-Kohout, Raymond Laflamme, Harold Ollivier 2003).
* Hardness of simulation proof (Fujii et al. 2014)
* Difficulty of simulation due to increasing Schmidt rank (Datta, Vidal 2007)
* Discord in DQC1: Datta, Shaji, Caves PRL 2008.
How much entanglement is necessary to quantum compute? For pure-state quantum computation, Jozsa and Linden showed some non-zero amount is necessary. In DQC1, not much bipartite entanglement is present across all bipartitions. But universal quantum computation also needs not require much bipartite entanglement, as shown by Van den Nest in this 2013 paper.
3- Measurement-based quantum computation (MBQC)
Description of model: this is an excellent review by Josza, this part of my lecture was based on section 2.1 of this paper by McKague. These short, self-contained lecture notes by Jozsa provide the best overview of the model for novices. Step by step we'll build the ingredients for MBQC. Single-bit Z teleportation. Gate teleportation idea by Gottesman and Chuang, simplified here using the 1-bit Z teleportation circuit. Concatenating series of single-bit gate teleportations we can apply an arbitrary single-qubit gate using teleportation (I skipped discussion about corrections for CZ gates, which is similar). Discussion about how corrections work and what's needed from the classical control computer.
Entanglement resources for MBQC: defining graph states. Cluster states, 3-qubit DFT example, role of Z measurements. Other known universal resources for MBQC (Gross et al.'s paper). Simulability of linear 1D cluster.
Time-ordering in MBQC, parallelizing Clifford gates in MBQC. We've seen that this parallelization carries over to the circuit model when we translate the MBQC implementation back into circuits.
Experimental implementations: topological error correction using eight-photon cluster state, single-site addressing of cold neutral atoms in Mott-insulator state in an optical lattice, percolation-inspired approach to MBQC with faulty CZs.
MBQC as a toy model for quantum spacetime (paper by Raussendorf et al.). How time-travel appears in MBQC (my paper with Elham Kashefi and Raphael Dias da Silva).
The so-called measurement-based classical computation (paper by Hoban et al.) discusses MBQC implementations of IQP circuits. The gate commutativity (in the circuit model) translates to MBQC as non-adaptativity.
Where does the power of MBQC comes from? Due to the neat separation between classical and quantum resources, it must come from the correlations exhibited by measurements of the cluster state. The connection with non-locality and contextuality has been studied in a few papers, for example this paper by Hoban et al. (on the relation with non-locality tests) and this paper by Raussendorf (relating MBQC with quantum contextuality).
4- Quantum computing with light
This review paper by Kok et al. lists much of the relevant literature, but is a bit old (2005). I won't cover continuous-variable systems (this is a good review), but will mention some ideas and include references to interesting recent work:
* Hybrid continuous- and discrete-variable systems - check out recent work by Furusawa's group, for example this paper on continuous-variable entanglement on a chip.
* Frequency combs from OPO light: Olivier Pfister's group generation of entanglement between 60 frequency modes.
* Time-domain CV entanglement of 10000 modes, in experiment by Furusawa's group.
Using the path degree of freedom: single rail and dual rail encodings. Single-qubit gates in the dual rail encoding.
KLM model = computation with linear optics and measurement feed-forward (Review by Kok et al.). Description of the model, the need for off-line state preparation and adaptativity. KLM = MBQC adapted to a photonic setup. New ideas based on MBQC, especially the Browne/Rudolph fusion gates. How KLM is related to MBQC (Popescu paper).
Review of connections we've found between linear optics and various types of restricted classes of quantum computational processes (I've added up a couple more: MBQC with measurements in Pauli bases, and mentioned matchgates, the theme of Jozsa's upcoming 3rd lecture).
5- Linear optics without adaptive measurements
Description of dynamics using permanents, deriving a new bosonic bunching rule. Boson sampling proposal by Arkhipov and Aaronson, its hardness of simulation. These lecture notes of a short course given by Scott Aaronson give an overview of the computational complexity of linear optics. 2 practical (partial) certification tests (Sciarrino group paper). Issues arising from some recent experiments (scattershot boson sampling, by Sciarrino et al.). Recent results in boson sampling: time-bin version, reprogrammable chip for universal linear optics, boson sampling with short chips, possible applications in metrology and simulation.
6- Other restricted models - I probably won't have time to cover this section.
6.1 Matchgates: description, relationship with non-interacting fermions, simulability. How to upgrade matchgates to universal quantum computation (Brod/Galvão papers, Brod/Childs paper). Compressed simulation scheme of Barbara Kraus.
6.2 Permutational quantum computation (Jordan paper).