Limitations of optimization algorithms on noisy quantum devices
- URL: http://arxiv.org/abs/2009.05532v1
- Date: Fri, 11 Sep 2020 17:07:26 GMT
- Title: Limitations of optimization algorithms on noisy quantum devices
- Authors: Daniel Stilck Franca, Raul Garcia-Patron
- Abstract summary: We present a transparent way of comparing classical algorithms to quantum ones running on near-term quantum devices.
Our approach is based on the combination of entropic inequalities that determine how fast the quantum state converges to the fixed point of the noise model.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recent technological developments have focused the interest of the quantum
computing community on investigating how near-term devices could outperform
classical computers for practical applications. A central question that remains
open is whether their noise can be overcome or it fundamentally restricts any
potential quantum advantage. We present a transparent way of comparing
classical algorithms to quantum ones running on near-term quantum devices for a
large family of problems that include optimization problems and approximations
to the ground state energy of Hamiltonians. Our approach is based on the
combination of entropic inequalities that determine how fast the quantum
computation state converges to the fixed point of the noise model, together
with established classical methods of Gibbs state sampling. The approach is
extremely versatile and allows for its application to a large variety of
problems, noise models and quantum computing architectures. We use our result
to provide estimates for a variety of problems and architectures that have been
the focus of recent experiments, such as quantum annealers, variational quantum
eigensolvers, and quantum approximate optimization. The bounds we obtain
indicate that substantial quantum advantages are unlikely for classical
optimization unless the current noise rates are decreased by orders of
magnitude or the topology of the problem matches that of the device. This is
the case even if the number of qubits increases substantially. We reach similar
but less stringent conclusions for quantum Hamiltonian problems.
Related papers
- Power Characterization of Noisy Quantum Kernels [52.47151453259434]
We show that noise may make quantum kernel methods to only have poor prediction capability, even when the generalization error is small.
We provide a crucial warning to employ noisy quantum kernel methods for quantum computation.
arXiv Detail & Related papers (2024-01-31T01:02:16Z) - 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) - Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
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.
arXiv Detail & Related papers (2023-10-04T17:53:55Z) - Fighting noise with noise: a stochastic projective quantum eigensolver [0.0]
We present a novel approach to estimating physical observables which leads to a two order of magnitude reduction in the required sampling of the quantum state.
The method can be applied to excited-state calculations and simulation for general chemistry on quantum devices.
arXiv Detail & Related papers (2023-06-26T09:22:06Z) - NP-hard but no longer hard to solve? Using quantum computing to tackle
optimization problems [1.1470070927586016]
We discuss the field of quantum optimization where we solve optimisation problems using quantum computers.
We demonstrate this through a proper use case and discuss the current quality of quantum computers.
We conclude with discussion on some recent quantum optimization breakthroughs and the current status and future directions.
arXiv Detail & Related papers (2022-12-21T12:56:37Z) - Anticipative measurements in hybrid quantum-classical computation [68.8204255655161]
We present an approach where the quantum computation is supplemented by a classical result.
Taking advantage of its anticipation also leads to a new type of quantum measurements, which we call anticipative.
In an anticipative quantum measurement the combination of the results from classical and quantum computations happens only in the end.
arXiv Detail & Related papers (2022-09-12T15:47:44Z) - Limitations of variational quantum algorithms: a quantum optimal
transport approach [11.202435939275675]
We obtain extremely tight bounds for standard NISQ proposals in both the noisy and noiseless regimes.
The bounds limit the performance of both circuit model algorithms, such as QAOA, and also continuous-time algorithms, such as quantum annealing.
arXiv Detail & Related papers (2022-04-07T13:58:44Z) - Quantum algorithms for quantum dynamics: A performance study on the
spin-boson model [68.8204255655161]
Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator.
variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware.
We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
arXiv Detail & Related papers (2021-08-09T18:00:05Z) - Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
We propose a resource and runtime efficient scheme termed quantum architecture search (QAS)
QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates.
We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
arXiv Detail & Related papers (2020-10-20T12:06:27Z) - 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) - Policy Gradient based Quantum Approximate Optimization Algorithm [2.5614220901453333]
We show that policy-gradient-based reinforcement learning algorithms are well suited for optimizing the variational parameters of QAOA in a noise-robust fashion.
We analyze the performance of the algorithm for quantum state transfer problems in single- and multi-qubit systems.
arXiv Detail & Related papers (2020-02-04T00:46:51Z)
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.