This is the true key question: what are the most important algorithms that would be accelerated by quantum computing?
Some candidates:
- Shor's algorithm: this one will actually make humanity worse off, as we will be forced into post-quantum cryptography that will likely be less efficient than existing classical cryptography to implement
- quantum algorithm for linear systems of equations, and related application of systems of linear equations
- Grover's algorithm: speedup not exponential. Still useful for anything?
- Quantum Fourier transform: TODO is the speedup exponential or not?
- Deutsch: solves an useless problem
- NISQ algorithms
Maybe there is some room for doubt because some applications might be way better in some implementations, but we should at least have a good general idea.
However, clear information on this really hard to come by, not sure why.
Whenever asked e.g. at: physics.stackexchange.com/questions/3390/can-anybody-provide-a-simple-example-of-a-quantum-computer-algorithm/3407 on Physics Stack Exchange people say the infinite mantra:
Lists:
- Quantum Algorithm Zoo: the leading list as of 2020
- quantum computing computational chemistry algorithms is the area that Ciro and many people are te most excited about is
- cstheory.stackexchange.com/questions/3888/np-intermediate-problems-with-efficient-quantum-solutions
- mathoverflow.net/questions/33597/are-there-any-known-quantum-algorithms-that-clearly-fall-outside-a-few-narrow-cla
Only NP-intermediate, which includes notably integer factorization:
- quantumcomputing.stackexchange.com/questions/16506/can-quantum-computer-solve-np-complete-problems
- www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf by Scott Aaronson
- cs.stackexchange.com/questions/130470/can-quantum-computing-help-solve-np-complete-problems
- www.quora.com/How-can-quantum-computing-help-to-solve-NP-hard-problems
The most comprehensive list is the amazing curated and commented list of quantum algorithms as of 2020.
There is no fundamental difference between them, a quantum algorithm is a quantum circuit, which can be seen as a super complicated quantum gate.
Perhaps the greats practical difference is that algorithms tend to be defined for an arbitrary number of N qubits, i.e. as a function for that each N produces a specific quantum circuit with N qubits solving the problem. Most named gates on the other hand have fixed small sizes.
Sample implementations:
Shor's algorithm Explained by minutephysics (2019)
Source. - 2023 www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html comments on "Factoring integers with sublinear resources on a superconducting quantum processor” arxiv.org/pdf/2212.12372.pdf
A group of Chinese researchers have just published a paper claiming that they can—although they have not yet done so—break 2048-bit RSA. This is something to take seriously. It might not be correct, but it’s not obviously wrong.We have long known from Shor’s algorithm that factoring with a quantum computer is easy. But it takes a big quantum computer, on the orders of millions of qbits, to factor anything resembling the key sizes we use today. What the researchers have done is combine classical lattice reduction factoring techniques with a quantum approximate optimization algorithm. This means that they only need a quantum computer with 372 qbits, which is well within what’s possible today. (The IBM Osprey is a 433-qbit quantum computer, for example. Others are on their way as well.)
Articles by others on the same topic
A quantum algorithm specifies quantum state preparation, a sequence of quantum gates and quantum measurements, and any classical computation controlling them. For a pure quantum state , computational-basis measurement returns with probability , as prescribed by the Born rule. David Deutsch formulated a universal quantum computer using unitary operators and measurement.[ref]
For example, one Hadamard gate prepares . Computational-basis measurement gives either bit with probability . Applying another Hadamard gate before measuring instead gives : the amplitudes for outcome one cancel by quantum interference. This illustrates why manipulating probability amplitudes matters; merely preparing a superposition does not reveal every component.
An analysis of algorithms must state the counted resources: quantum gate count, number of qubits, quantum state preparation cost and repetitions needed for the required probability of a correct result. Quantum query complexity counts quantum oracle calls separately; one such call need not be one elementary quantum gate.
A quantum algorithm is a step-by-step procedure, designed to be executed on a quantum computer, that utilizes the principles of quantum mechanics to solve problems more efficiently than classical algorithms. Quantum algorithms leverage unique quantum phenomena, such as superposition and entanglement, which allow for complex calculations to be performed in parallel and enable the exploration of vast solution spaces more rapidly.