Quantum algorithm

[citation needed] The Deutsch–Jozsa algorithm solves a black-box problem that requires exponentially many queries to the black box for any deterministic classical computer, but can be done with a single query by a quantum computer.

However, when comparing bounded-error classical and quantum algorithms, there is no speedup, since a classical probabilistic algorithm can solve the problem with a constant number of queries with small probability of error.

There are efficient quantum algorithms known for the Abelian hidden subgroup problem.

Since the discrete logarithm problem reduces to Gauss sum estimation, an efficient classical algorithm for estimating Gauss sums would imply an efficient classical algorithm for computing discrete logarithms, which is considered unlikely.

Applications of amplitude amplification usually lead to quadratic speedups over the corresponding classical algorithms.

Theorists have considered a hypothetical generalization of a standard quantum computer that could access the histories of the hidden variables in Bohmian mechanics.

However, neither search method would allow either model of quantum computer to solve NP-complete problems in polynomial time.

It solves the problem of counting the number of marked entries in an unordered list, instead of just detecting whether one exists.

A framework for the creation of quantum walk algorithms exists and is a versatile tool.

[21] The Boson Sampling Problem in an experimental configuration assumes[22] an input of bosons (e.g., photons) of moderate number that are randomly scattered into a large number of output modes, constrained by a defined unitarity.

[23] The problem is then to produce a fair sample of the probability distribution of the output that depends on the input arrangement of bosons and the unitarity.

In 2014, it was proposed[25] that existing technology and standard probabilistic methods of generating single-photon states could be used as an input into a suitable quantum computable linear optical network and that sampling of the output probability distribution would be demonstrably superior using quantum algorithms.

In 2015, investigation predicted[26] the sampling problem had similar complexity for inputs other than Fock-state photons and identified a transition in computational complexity from classically simulable to just as hard as the Boson Sampling Problem, depending on the size of coherent amplitude inputs.

The optimal algorithm was put forth by Andris Ambainis,[27] and Yaoyun Shi first proved a tight lower bound when the size of the range is sufficiently large.

[28] Ambainis[29] and Kutin[30] independently (and via different proofs) extended that work to obtain the lower bound for all functions.

The problem is to evaluate the formula, which is the output of the root node, given oracle access to the input.

No better quantum algorithm for this case was known until one was found for the unconventional Hamiltonian oracle model.

The interest in this context lies in the query complexity, which is the number of oracle calls needed to solve the problem.

[38] The complexity class BQP (bounded-error quantum polynomial time) is the set of decision problems solvable by a quantum computer in polynomial time with error probability of at most 1/3 for all instances.

Witten had shown that the Chern-Simons topological quantum field theory (TQFT) can be solved in terms of Jones polynomials.

Efficient (i.e., polynomial-time) quantum algorithms have been developed for simulating both Bosonic and Fermionic systems,[42] as well as the simulation of chemical reactions beyond the capabilities of current classical supercomputers using only a few hundred qubits.

[44] In addition to its intrinsic interest, this result has led to efficient quantum algorithms for estimating quantum topological invariants such as Jones[45] and HOMFLY polynomials,[46] and the Turaev-Viro invariant of three-dimensional manifolds.

[47] In 2009, Aram Harrow, Avinatan Hassidim, and Seth Lloyd, formulated a quantum algorithm for solving linear systems.

The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.

Hybrid Quantum/Classical Algorithms combine quantum state preparation and measurement with classical optimization.

[49] These algorithms generally aim to determine the ground-state eigenvector and eigenvalue of a Hermitian operator.

[50] The algorithm makes use of classical optimization of quantum operations to maximize an "objective function."

The variational quantum eigensolver (VQE) algorithm applies classical optimization to minimize the energy expectation value of an ansatz state to find the ground state of a Hermitian operator, such as a molecule's Hamiltonian.

[52] The contracted quantum eigensolver (CQE) algorithm minimizes the residual of a contraction (or projection) of the Schrödinger equation onto the space of two (or more) electrons to find the ground- or excited-state energy and two-electron reduced density matrix of a molecule.

[53] It is based on classical methods for solving energies and two-electron reduced density matrices directly from the anti-Hermitian contracted Schrödinger equation.