Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Bulletin of the American Physical Society

A device-oriented optimizer for solving ground state problems on an approximate quantum computer, Part I: Theory

Antonio Mezzacapo, Abhinav Kandala, Kristan Temme, Sergey B. Bravyi, Maika Takita, José Chavez-Garcia, Antonio C 'orcoles, John A. Smolin, Jerry M. Chow, Jay Gambetta

Published Mar 14, 2017• 0 citations
OpenAlex

Related papers

A device-oriented optimizer for solving ground state problems on an approximate quantum computer, Part II: Experiments for interacting spin and molecular systems

Abhinav Kandala, Antonio Mezzacapo, Kristan Temme +7 more

Bulletin of the American Physical Society•Mar 14, 2017•0 citations

Designing, programming, and optimizing a (small) quantum computer

Krysta M. Svore

Bulletin of the American Physical Society•Mar 13, 2017•0 citations

Iterative quantum algorithm for combinatorial optimization based on quantum gradient descent

Xin Yi, Jingyu Huo, Yong‐Pan Gao +3 more

Combinatorial optimization has wide and high-value applications in many fields of science and industry, but solving general combinatorial optimization problems is non-deterministic polynomial time (NP) hard. Many such problems can be mapped onto the ground-state-search problems of the Ising model. Here, an iterative quantum algorithm based on quantum gradient descent to solve combinatorial optimization problems is introduced, where the initial state of a quantum register evolves over several iterations to a good approximation of the Ising-Hamiltonian ground state. We verified the effectiveness of the proposed algorithm in solving the MaxCut problem for different types of undirected graphs by numerical simulations, and analyzed the robustness of the algorithm to errors by simulating random error and Gaussian error. We compared the performance of the algorithm with the quantum approximate optimization algorithm, and the results indicate that the proposed algorithm has comparable convergence performance. We also verified the feasibility of the algorithm by conducting experiments on a real quantum computer through the quantum cloud platform. Our work provides a potential method for solving combinatorial optimization problems on future quantum devices without the use of complex classical optimization loops.

Results in Physics•Nov 20, 2023•17 citations

Approximated quantum computing and its application for near-term quantum devices

Keisuke Fujii

The Japan Society of Applied Physics•Feb 8, 2018•0 citations

Combinatorial Optimization on Gate Model Quantum Computers: A Survey

Ehsan Zahedinejad, Arman Zaribafiyan

The advent of quantum computing processors with possibility to scale beyond experimental capacities magnifies the importance of studying their applications. Combinatorial optimization problems can be one of the promising applications of these new devices. These problems are recurrent in industrial applications and they are in general difficult for classical computing hardware. In this work, we provide a survey of the approaches to solving different types of combinatorial optimization problems, in particular quadratic unconstrained binary optimization (QUBO) problems on a gate model quantum computer. We focus mainly on four different approaches including digitizing the adiabatic quantum computing, global quantum optimization algorithms, the quantum algorithms that approximate the ground state of a general QUBO problem, and quantum sampling. We also discuss the quantum algorithms that are custom designed to solve certain types of QUBO problems.

arXiv:1708.05294•Aug 16, 2017•29 citations

Training Variational Quantum Algorithms Is NP-Hard

Lennart Bittel, Martin Kliesch

Variational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum approximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parametrized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming that P≠NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima This means gradient and higher order descent algorithms will generally converge to far from optimal solutions.

arXiv:2101.07267•Physical Review Letters•Sep 17, 2021•397 citations
Combinatorial optimization has wide and high-value applications in many fields of science and industry, but solving general combinatorial optimization problems is non-deterministic polynomial time (NP) hard. Many such problems can be mapped onto the ground-state-search problems of the Ising model. Here, an iterative quantum algorithm based on quantum gradient descent to solve combinatorial optimization problems is introduced, where the initial state of a quantum register evolves over several iterations to a good approximation of the Ising-Hamiltonian ground state. We verified the effectiveness of the proposed algorithm in solving the MaxCut problem for different types of undirected graphs by numerical simulations, and analyzed the robustness of the algorithm to errors by simulating random error and Gaussian error. We compared the performance of the algorithm with the quantum approximate optimization algorithm, and the results indicate that the proposed algorithm has comparable convergence performance. We also verified the feasibility of the algorithm by conducting experiments on a real quantum computer through the quantum cloud platform. Our work provides a potential method for solving combinatorial optimization problems on future quantum devices without the use of complex classical optimization loops.
The advent of quantum computing processors with possibility to scale beyond experimental capacities magnifies the importance of studying their applications. Combinatorial optimization problems can be one of the promising applications of these new devices. These problems are recurrent in industrial applications and they are in general difficult for classical computing hardware. In this work, we provide a survey of the approaches to solving different types of combinatorial optimization problems, in particular quadratic unconstrained binary optimization (QUBO) problems on a gate model quantum computer. We focus mainly on four different approaches including digitizing the adiabatic quantum computing, global quantum optimization algorithms, the quantum algorithms that approximate the ground state of a general QUBO problem, and quantum sampling. We also discuss the quantum algorithms that are custom designed to solve certain types of QUBO problems.
Variational quantum algorithms are proposed to solve relevant computational problems on near term quantum devices. Popular versions are variational quantum eigensolvers and quantum approximate optimization algorithms that solve ground state problems from quantum chemistry and binary optimization problems, respectively. They are based on the idea of using a classical computer to train a parametrized quantum circuit. We show that the corresponding classical optimization problems are NP-hard. Moreover, the hardness is robust in the sense that, for every polynomial time algorithm, there are instances for which the relative error resulting from the classical optimization problem can be arbitrarily large assuming that P≠NP. Even for classically tractable systems composed of only logarithmically many qubits or free fermions, we show the optimization to be NP-hard. This elucidates that the classical optimization is intrinsically hard and does not merely inherit the hardness from the ground state problem. Our analysis shows that the training landscape can have many far from optimal persistent local minima This means gradient and higher order descent algorithms will generally converge to far from optimal solutions.