Algorithms and benchmarks

14 algorithm families shown; 0 further algorithms shown.

Algorithm families

• Fault-tolerant Factoring and cryptanalysis

  Shor's algorithm: factoring and discrete logarithms

  Finds the prime factors of a large integer, or a discrete logarithm, in time that grows only polynomially with the number of digits. A large enough error-corrected quantum computer running it would break RSA and elliptic-curve public-key cryptography, which is why post-quantum cryptography is being deployed now.

  Platforms: Superconducting qubits, Trapped ions, Photonic qubits

  6 sourced resource estimates · 2 documented demonstrations

  Details, requirements and sources Shor's algorithm: factoring and discrete logarithms

• Fault-tolerant Search

  Grover search and amplitude amplification

  Finds a marked item among N possibilities with about the square root of N checks instead of about N. Amplitude amplification generalises the idea to speed up any procedure that succeeds with some probability.

  Platforms: Trapped ions, Superconducting qubits

  0 sourced resource estimates · 1 documented demonstration

  Details, requirements and sources Grover search and amplitude amplification

• Fault-tolerant Estimation and Monte Carlo

  Amplitude estimation and quantum Monte Carlo integration

  Estimates an expected value, such as the price of a financial derivative or a risk measure, with fewer samples than classical Monte Carlo simulation. Here quantum Monte Carlo means this speedup of Monte Carlo integration, not the classical quantum Monte Carlo methods of physics.

  Platforms: Superconducting qubits

  1 sourced resource estimate · 1 documented demonstration

  Details, requirements and sources Amplitude estimation and quantum Monte Carlo integration

• Fault-tolerant Linear algebra and eigenvalues

  Quantum phase estimation

  Measures an eigenvalue of a unitary operation, such as the energy of a molecule encoded as a phase. It is the core subroutine of Shor’s algorithm, of fault-tolerant chemistry and of many linear-algebra algorithms.

  Platforms: Superconducting qubits

  0 sourced resource estimates · 1 documented demonstration

  Details, requirements and sources Quantum phase estimation

• Fault-tolerant Simulation of physical systems

  Hamiltonian simulation: product formulas, qubitization and QSVT

  Reproduces how a quantum system evolves in time on a gate-based quantum computer: spins, electrons in materials, molecules or nuclear matter. This is the application Feynman had in mind, and the one with the strongest case for exponential speedups.

  Platforms: Superconducting qubits

  1 sourced resource estimate · 1 documented demonstration

  Details, requirements and sources Hamiltonian simulation: product formulas, qubitization and QSVT

• Fault-tolerant Chemistry and materials

  Electronic structure on fault-tolerant computers (catalysts such as FeMoco)

  Computes energies of molecules and materials to chemical accuracy where classical methods struggle, such as the iron-molybdenum cofactor (FeMoco) of nitrogenase, which fixes nitrogen in nature. It combines Hamiltonian simulation with phase estimation.

  Platforms: Superconducting qubits

  1 sourced resource estimate · 1 documented demonstration

  Details, requirements and sources Electronic structure on fault-tolerant computers (catalysts such as FeMoco)

• Noisy intermediate-scale (NISQ) Chemistry and materials

  Variational quantum eigensolver (VQE)

  A hybrid method that estimates ground-state energies of molecules and magnets with short circuits whose parameters a classical optimiser tunes. It was designed for noisy devices without error correction.

  Platforms: Photonic qubits, Superconducting qubits

  0 sourced resource estimates · 2 documented demonstrations

  Details, requirements and sources Variational quantum eigensolver (VQE)

• Noisy intermediate-scale (NISQ) Chemistry and materials

  Sample-based quantum diagonalisation with supercomputers

  A quantum-centric supercomputing workflow: a quantum processor samples electronic configurations and a supercomputer diagonalises the Hamiltonian in the space they span, giving upper bounds for the ground-state energy.

  Platforms: Superconducting qubits

  0 sourced resource estimates · 1 documented demonstration

  Details, requirements and sources Sample-based quantum diagonalisation with supercomputers

• Noisy intermediate-scale (NISQ) Optimisation

  Quantum approximate optimisation algorithm (QAOA)

  A variational method for combinatorial optimisation, such as finding a large cut in a graph or scheduling, with circuits that alternate between the cost function and a mixing step.

  Platforms: Superconducting qubits, Neutral atoms

  0 sourced resource estimates · 1 documented demonstration

  Details, requirements and sources Quantum approximate optimisation algorithm (QAOA)

• Noisy intermediate-scale (NISQ) Machine learning

  Quantum kernel methods for machine learning

  Uses a quantum circuit to map data into a large feature space and estimates similarities (kernels) between data points there, for use in a classical support vector machine.

  Platforms: Superconducting qubits

  0 sourced resource estimates · 1 documented demonstration

  Details, requirements and sources Quantum kernel methods for machine learning

• Noisy intermediate-scale (NISQ) Machine learning

  Variational quantum neural networks

  Parameterised quantum circuits trained like neural networks for classification, regression or generative modelling, often as one layer of a hybrid classical model.

  Platforms: Neutral atoms, Superconducting qubits

  0 sourced resource estimates · 1 documented demonstration

  Details, requirements and sources Variational quantum neural networks

• Noisy intermediate-scale (NISQ) Sampling and quantum advantage tests

  Random circuit sampling

  Runs randomly chosen circuits and samples their output bit strings, a task designed to be hard for classical computers; it was used for the first claims of quantum advantage and is also a benchmark (cross-entropy benchmarking).

  Platforms: Superconducting qubits

  0 sourced resource estimates · 2 documented demonstrations

  Details, requirements and sources Random circuit sampling

• Fault-tolerant Error correction (enabling)

  Surface code error correction

  The leading quantum error-correcting code for chips with nearest-neighbour connections: many physical qubits on a 2D grid encode one logical qubit, and repeated measurements detect errors that a classical decoder corrects in real time.

  Platforms: Superconducting qubits, Neutral atoms

  0 sourced resource estimates · 1 documented demonstration

  Details, requirements and sources Surface code error correction

• Fault-tolerant Error correction (enabling)

  Bosonic cat qubits with repetition codes

  Cat qubits store information in superpositions of coherent states of a microwave resonator; bit flips are suppressed exponentially with photon number, so only phase flips need a simple repetition code.

  Platforms: Superconducting qubits

  1 sourced resource estimate · 0 documented demonstrations

  Details, requirements and sources Bosonic cat qubits with repetition codes