Quantum algorithms: A survey of applications and end-to-end complexities
- URL: http://arxiv.org/abs/2310.03011v1
- Date: Wed, 4 Oct 2023 17:53:55 GMT
- Title: Quantum algorithms: A survey of applications and end-to-end complexities
- Authors: Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias,
Chi-Fang Chen, Andr\'as Gily\'en, Connor T. Hann, Michael J. Kastoryano, Emil
T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, Fernando G.
S. L. Brand\~ao
- Abstract summary: The anticipated applications of quantum computers span across science and industry.
We present a survey of several potential application areas of quantum algorithms.
We outline the challenges and opportunities in each area in an "end-to-end" fashion.
- Score: 90.05272647148196
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The anticipated applications of quantum computers span across science and
industry, ranging from quantum chemistry and many-body physics to optimization,
finance, and machine learning. Proposed quantum solutions in these areas
typically combine multiple quantum algorithmic primitives into an overall
quantum algorithm, which must then incorporate the methods of quantum error
correction and fault tolerance to be implemented correctly on quantum hardware.
As such, it can be difficult to assess how much a particular application
benefits from quantum computing, as the various approaches are often sensitive
to intricate technical details about the underlying primitives and their
complexities. Here we present a survey of several potential application areas
of quantum algorithms and their underlying algorithmic primitives, carefully
considering technical caveats and subtleties. We outline the challenges and
opportunities in each area in an "end-to-end" fashion by clearly defining the
problem being solved alongside the input-output model, instantiating all
"oracles," and spelling out all hidden costs. We also compare quantum solutions
against state-of-the-art classical methods and complexity-theoretic limitations
to evaluate possible quantum speedups.
The survey is written in a modular, wiki-like fashion to facilitate
navigation of the content. Each primitive and application area is discussed in
a standalone section, with its own bibliography of references and embedded
hyperlinks that direct to other relevant sections. This structure mirrors that
of complex quantum algorithms that involve several layers of abstraction, and
it enables rapid evaluation of how end-to-end complexities are impacted when
subroutines are altered.
Related papers
- Quantum Information Processing with Molecular Nanomagnets: an introduction [49.89725935672549]
We provide an introduction to Quantum Information Processing, focusing on a promising setup for its implementation.
We introduce the basic tools to understand and design quantum algorithms, always referring to their actual realization on a molecular spin architecture.
We present some examples of quantum algorithms proposed and implemented on a molecular spin qudit hardware.
arXiv Detail & Related papers (2024-05-31T16:43:20Z) - What is computable and non-computable in the quantum domain: 7 statements and 3 conjectures [0.7892577704654171]
There is no universal approach that helps to define a scope of problems that quantum computers are able to speed up.
On the one hand, the class of quantum states that is of interest for quantum computing should be complex.
On the other hand, such quantum states should be reachable on a practical quantum computer.
arXiv Detail & Related papers (2024-03-25T15:47:35Z) - State-Averaged Orbital-Optimized VQE: A quantum algorithm for the
democratic description of ground and excited electronic states [0.0]
The SA-OO-VQE package aims to answer both problems with its hybrid quantum-classical conception based on a typical Variational Quantum Eigensolver approach.
The SA-OO-VQE has the ability to treat degenerate (or quasi-degenerate) states on the same footing, thus avoiding known numerical optimization problems around avoided crossings or conical intersections.
arXiv Detail & Related papers (2024-01-22T12:16:37Z) - Where Quantum Complexity Helps Classical Complexity [2.5751645168025297]
Adapting problem-solving strategies is crucial to harness the full potential of quantum computing.
This paper concentrates on aggregating prior research efforts dedicated to solving intricate classical computational problems through quantum computing.
arXiv Detail & Related papers (2023-12-16T16:02:21Z) - A Practitioner's Guide to Quantum Algorithms for Optimisation Problems [0.0]
NP-hard optimisation problems are common in industrial areas such as logistics and finance.
This paper aims to provide a comprehensive overview of the theory of quantum optimisation techniques.
It focuses on their near-term potential for noisy intermediate scale quantum devices.
arXiv Detail & Related papers (2023-05-12T08:57:36Z) - Quantum Machine Learning: from physics to software engineering [58.720142291102135]
We show how classical machine learning approach can help improve the facilities of quantum computers.
We discuss how quantum algorithms and quantum computers may be useful for solving classical machine learning tasks.
arXiv Detail & Related papers (2023-01-04T23:37:45Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Variational Quantum Algorithms for Computational Fluid Dynamics [0.0]
Variational quantum algorithms are particularly promising since they are comparatively noise tolerant.
We show how variational quantum algorithms can be utilized in computational fluid dynamics.
We argue that a quantum advantage over classical computing methods could be achieved by the end of this decade.
arXiv Detail & Related papers (2022-09-11T18:49:22Z) - Electronic structure with direct diagonalization on a D-Wave quantum
annealer [62.997667081978825]
This work implements the general Quantum Annealer Eigensolver (QAE) algorithm to solve the molecular electronic Hamiltonian eigenvalue-eigenvector problem on a D-Wave 2000Q quantum annealer.
We demonstrate the use of D-Wave hardware for obtaining ground and electronically excited states across a variety of small molecular systems.
arXiv Detail & Related papers (2020-09-02T22:46:47Z) - An Application of Quantum Annealing Computing to Seismic Inversion [55.41644538483948]
We apply a quantum algorithm to a D-Wave quantum annealer to solve a small scale seismic inversions problem.
The accuracy achieved by the quantum computer is at least as good as that of the classical computer.
arXiv Detail & Related papers (2020-05-06T14:18:44Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.