1980: Quantum Computing Proposed

Quantum computers were theorised by Benioff, providing the first theoretical quantum mechanical framework of a reversible Turing machine. Richard Feynman proposed the use of these quantum computers to efficiently simulate quantum systems, avoiding the exponential resource requirements when using classical computers. Lloyd subsequently confirmed that quantum computers can efficiently simulate any local quantum system. Extending this, Deutsch later showed that, unlike classical computers, quantum computers can efficiently simulate any physical process.

Benioff: https://link.springer.com/article/10.1007/BF01011339

Feynman: https://catonmat.net/ftp/simulating-physics-with-computers-richard-feynman.pdf

Lloyd: https://www.science.org/doi/10.1126/science.273.5278.1073

Deutsch: https://royalsocietypublishing.org/doi/10.1098/rspa.1985.0070

This book, affectionately known as Mike and Ike, serves as a good introduction to quantum computing.

1985: Deutsch’s Algorithm

One of the first quantum algorithms that provided a speed up over classical counterparts was developed by David Deutsch. The algorithm would determine if a two-bit function was balanced or constant with probabilistic success using only one call to the function. This was an improvement over the best classical algorithm which requires two calls. A constant function returns the same value for all inputs whilst balanced functions return one of two values, each for half the possible inputs.

Reference: David Deutsch describes a quantum algorithm for determining if a function is constant or balanced. https://royalsocietypublishing.org/doi/10.1098/rspa.1985.0070

This video frames Deutsch’s problem in an easy-to-understand manner.

1988: Quantum Annealing

A form of non-universal quantum computation was proposed for finding a global minimum of a function using quantum tunnelling. By slowly varying a Hamiltonian in the time dependent Schrödinger equation, the system evolves into the solution represented by the smallest eigenvalue with high probability.

Reference: Apolloni et al. present a numerical implementation of quantum annealing. https://www.researchgate.net/publication/250309136_A_numerical_implementation_of_quantum_annealing

D-wave documentation provides motivation for quantum annealing, what it is, and how it works.

A‌bove: An energy diagram displaying the process of quantum annealing. This is a process where the Hamiltonian of a given system is slowly varied in time whilst remaining in the lowest energy eigenstate. The energy landscape of the system will evolve such that there will be distinct eigenvalues. This is represented by the parabolic curve (top, lightest grey) transitioning to the middle and then bottom shapes, where the right-hand side represents the global minimum energy eigenvalue. The process of quantum annealing takes advantage of quantum tunnelling to allow the solution to rest in the lowest eigenvalue without having to climb up and over the middle peak as shown in the classical path as in simulated annealing.

1989: Circuit Based Quantum computation

A type of quantum computation analogous to classical computation was formulated whereby initialisation, logical gates, and measurements are sequentially applied to the qubits to implement a specific algorithm. This model is universal - it can run any quantum algorithm.

Reference: https://royalsocietypublishing.org/doi/pdf/10.1098/rspa.1989.0099

An overview from Qiskit on quantum circuits.

Above: An example circuit diagram for quantum computing. Each horizontal line represents one qubit with logical operations indicated by the boxes with time passing from left to right. The type of operation is shown by the letters in the box. Operations involving more than one qubit are indicated by vertical lines, or boxes spanning multiple qubits, and symbols indicating the type of operation being applied – for instance a dot indicates that this qubit is the target of an operations that is only applied if a different qubit, the control qubit (circle with cross in), is in a specific state. All operations have their own symbol meaning any algorithm can be represented as a quantum circuit diagram. Other symbols shown include SWAP gates, measurements and operations that depend on measurement outcomes. 

1992: Deutsch-Jozsa Algorithm

A deterministic generalisation of Deutsch’s algorithm was proposed giving an exponential speed up over the best known classical algorithm.

Reference: David Deutsch and Richard Jozsa publish a paper generalising Deutsch’s algorithm. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.655.5997

This set of lecture notes from Knuth provide a concrete explanation of the Deutsch-Jozsa algorithm.

1994: Quantum Fourier Transform

The quantum Fourier transform, formulated by Coppersmith, is a critical algorithm underpinning the speedups from many quantum algorithms. Requiring a polynomial number of operations to complete, the quantum Fourier transform provides an exponential speedup over the classical Fourier transform when performing operations in superpositions. Despite the possible speedups, it was shown by researchers at the Universities of Oxford and Bristol that there are some cases when the quantum Fourier transform and its variants can be efficiently simulated classically.

Reference: https://arxiv.org/abs/quant-ph/0201067

A run through of the derivation of QFT as well as a presentation of the quantum circuit for QFT was presented as part of the Qiskit global summer school in July 2020.

Above: A 2-qubit circuit diagram for implementing the quantum Fourier transform. Each horizontal line is a qubit, and this entire circuit consists of four gates. This uses two Hadamard gates (H), which puts qubits into superposition, a rotation gate (R₁) which is shown on the right (a 2x2 matrix as there are 2 qubits), and a SWAP gate (X’s with vertical line), which swaps the states of both qubits. As the R₁ gate is a controlled gate, it will only act on the first qubit (target, R₁ ) if the second qubit (control, black filled circle) is in the ‘1’ state. This circuit can be expanded to more qubits by adding a copy of this circuit to the left-hand side (before the first H in the diagram) and using different rotation gates.

1994: Shor’s Algorithm

A quantum algorithm for prime factoring was formulated by Shor, providing an exponential speedup compared to the most efficient known classical algorithm, the general number sieve. This algorithm relies on speedups from the quantum Fourier transform and modular exponentiation. Shor’s algorithm has implications for classical encryption methods that rely on a public-key encryption scheme, whereby security is derived from the classical complexity of prime number factoring. Shor’s paper kickstarted research into building a fault tolerant quantum computer and the field of post-quantum cryptography.

Reference: https://ieeexplore.ieee.org/document/365700

A video from minutephysics that explains the workings of Shor’s algorithm. A page on Quantiki motivating Shor’s algorithm, explaining which steps can be done classically and which require a quantum computer.

1995: First Quantum Error Correcting Codes

Quantum computers are highly susceptible to noise, meaning qubits need protection against errors. The laws of quantum mechanics prevent the use of classical error correction protocols, requiring quantum compatible protocols. Shor and Steane independently formulated the first quantum error correcting codes. Shor’s code encoded one logical qubit across nine physical qubits, protecting against arbitrary errors on one qubit. Steane’s more general formulation provided the same protection with only seven qubits using a Hamming code.

Shor and Steane independently formulate schemes for quantum error correction.

Shor: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.52.R2493

Steane: https://royalsocietypublishing.org/doi/10.1098/rspa.1996.0136

An introduction to quantum error correction protocols is provided by Dr Roffe, as well as a lecture from Shor explaining quantum error correcting codes and fault tolerance.

1995: Quantum Phase Estimation

A quantum algorithm which harnesses the quantum Fourier transform was proposed by Kitaev to estimate the phase of a quantum state and is widely utilised as a quantum subroutine. 

Reference: https://arxiv.org/abs/quant-ph/9511026

An explanation of quantum phase estimation from the Qiskit textbook.

1996: Grover’s Algorithm

Grover devised a quantum algorithm that provides a quadratic speedup compared to the best classical algorithm for unstructured search problems. Grover’s algorithm can also be used to speed up classical unstructured search problems in the case where the solution can be checked efficiently.

Reference: https://arxiv.org/abs/quant-ph/9605043

A video explanation of Grover’s algorithm for unstructured search problems.

1997: Topological Quantum Comp

Kitaev proposed a method of fault tolerant quantum computation using topological features, with high resilience against errors by distributing qubits across a toroid. In later work with Bravyi, they developed a simplified planar version known as the surface code, which became one of the most predominant error correction schemes.

Reference: https://www.sciencedirect.com/science/article/pii/S0003491602000180?via%3Dihub

An excerpt from a lecture given by Professor Preskill on topological quantum computers. A paper by Lahtinen and Pachos give a more detailed introduction to topological quantum computation.

Above: A diagram showing the definition of the primal and dual types of logical qubits. In topological quantum computing, logical qubits are associated with a pair of defects, which are regions of qubits measured in the Z basis. A defect must have a boundary of either primal type or dual type.

2001: Linear Optical Quantum Computing

Knill, Laflamme and Milburn (KLM) devised a scheme for quantum computation requiring only linear optical components such as directional couplers and phase shifters, with the necessary non-linearity induced by projective measurements and ancilla photons. This avoids the challenge of implementing nonlinear interactions, providing a theoretically scalable pathway to optical quantum computation, at the expense of practically achievable determinism.

2003: Measurement Based Quantum Computing

Raussendorf and Briegel devised a form of universal quantum computation known as measurement-based quantum computing, by performing single qubit measurements on a highly entangled system known as a cluster state. This scheme is ideal for photonics, providing a more resource efficient and practically achievable alternative than the traditional KLM scheme.

Reference: https://journals.aps.org/pra/abstract/10.1103/PhysRevA.68.022312

A lecture on MBQC as part of Bristol’s own BQIT conference in 2021. Jozsa provides a theoretically motivated introduction to MBQC.

A‌bove: A diagram showing how computation is performed on a lattice of qubits using MBQC. Once a large cluster state of qubits is made, all qubits are measured one column at a time. Instead of changing the state of the qubit by applying logic gates, as in the circuit model, operations are performed by choosing different measurements for all the qubits. When each column of the cluster state is measured the information in that column is moved to the next column, up to the application of a local operation. Z measurements remove qubits from the lattice that are not needed in the computation and the arrows indicate the type of measurement made on each qubit.  Each highlighted yellow box is analogous to one of the qubits in the circuit model with vertical connections being the equivalent of two qubit operations.

2008: HHL Algorithm

Harrow, Hassidim and Lloyd proposed an efficient quantum algorithm for solving large systems of linear equations. Their algorithm requires the input and output to be given as quantum states. The HHL algorithm has since been used as a subroutine in many other quantum algorithms, such as for solving differential equations, and in quantum machine learning.

Harrow, Hassidim and Lloyd publish a paper where they describe a quantum algorithm for solving systems of linear equations. https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.103.150502

A paper offering a step-by-step breakdown of the HHL algorithm.

2011: Boson Sampling Proposed

Aaronson and Arkhipov proposed a method of proving quantum advantage by generating samples from a distribution that is classically hard to simulate. Whilst this is a non-universal method of quantum computation, it provided a useful benchmarking tool for the progression of quantum hardware beyond what was possible classically.

Aaronson and Arkhipov present the problem of boson sampling for demonstrating quantum advantage. https://arxiv.org/abs/1011.3245

A paper offering an introduction to Boson sampling. A lecture on Gaussian boson sampling – a variation on the boson sampling problem where the input states are Gaussian.

2014: Variational Quantum Eigensolver

A hybrid quantum-classical algorithm for finding the ground state energies of a Hamiltonian was developed. This is a key problem in quantum chemistry and is one of the most promising applications of near-term quantum computing. The scheme operates via classical optimisation updating the ansatz for a quantum algorithm.

The variational quantum eigensolver for computing the ground state energy of a Hamiltonian is described and demonstrated. https://www.nature.com/articles/ncomms5213

A comprehensive review on variational quantum eigensolvers.

2015: Quantum Speedup of Monte Carlo methods

Montanaro proposed a quantum algorithm for Monte Carlo methods that provides a near-quadratic speed up over the best-known classical algorithm. Monte Carlo algorithms utilise randomness to estimate solutions to problems that are difficult to solve deterministically, with uses in fields from statistical mechanics to mathematical finance.

Montanaro details a quantum algorithm offering a quantum speedup for Monte Carlo methods. https://royalsocietypublishing.org/doi/10.1098/rspa.2015.0301

A video from Professor Ceperley giving an overview of classical and quantum Monte Carlo methods.

2021: Fusion Based Quantum Computing

PsiQuantum developed a universal form of fault tolerant quantum computation in which qubits are topologically encoded within a cluster state. The generation of this cluster state processes the information as well as facilitating error correction. Whilst created for use in PsiQuantum's photonic quantum processors, the paradigm is hardware agnostic.

A team of PsiQuantum researchers introduce fusion-based quantum computation. https://arxiv.org/abs/2101.09310

A talk on FBQC from one of the PsiQuantum researchers at the Quantum Information Processing (QIP) conference in 2021.

‌Above: A 3D cube showing connections between qubits in the cluster state after fusion has occurred, which encodes and processes the information while creating this state. This fusion-based quantum computing was originally intended for use in photonic quantum computers but can be applied to any quantum computing hardware.