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

arXiv:2307.02461 · Physical Review A

Landscape approximation of low-energy solutions to binary optimization problems

Benjamin Y. L. Tan, Beng Yee Gan, Daniel Leykam, Dimitris G. Angelakis

Published Jan 26, 2024• 0 citations
arXivHTMLPDF

Abstract

We show how the localization landscape, originally introduced to bound low-energy eigenstates of disordered wave media and many-body quantum systems, can form the basis for hardware-efficient quantum algorithms for solving binary optimization problems. Many binary optimization problems can be cast as finding low-energy eigenstates of Ising Hamiltonians. First, we apply specific perturbations to the Ising Hamiltonian such that the low-energy modes are bounded by the localization landscape. Next, we demonstrate how a variational method can be used to prepare and sample from the peaks of the localization landscape. Numerical simulations of problems of up to ten binary variables show that the localization landscape-based sampling can outperform quantum approximate optimization algorithm (QAOA) circuits of similar depth, as measured in terms of the probability of sampling the exact ground state.

DOI
10.1103/physreva.109.012433

Related papers

Energy landscapes for the quantum approximate optimization algorithm

Choy Boy, David J. Wales

Variational quantum algorithms (VQAs) have demonstrated considerable potential in solving NP-hard combinatorial problems in the contemporary noisy intermediate-scale quantum (NISQ) era. The quantum approximate optimization algorithm (QAOA) is one such algorithm, used in solving the maximum cut (Max-Cut) problem for a given graph by successive implementation of L quantum circuit layers within a corresponding Trotterized ansatz. The challenge of exploring the cost function of VQAs arising from an exponential proliferation of local minima with increasing circuit depth has been well documented. However, fewer studies have investigated the impact of circuit depth on QAOA performance in finding the correct Max-Cut solution. Here we employ basin-hopping global optimization methods to navigate the energy landscapes for QAOA ansätze for various graphs, and analyze QAOA performance in finding the correct Max-Cut solution. The structure of the solution space is also investigated using discrete path sampling to build databases of local minima and the transition states that connect them, providing insightful visualizations using disconnectivity graphs. We find that the corresponding landscapes generally have a single funnel organization, which makes it relatively straightforward to locate low-lying minima with good Max-Cut solution probabilities. In some cases below the adiabatic limit the second lowest local minimum may even yield a higher solution probability than the global minimum. This important observation has motivated us to develop broader metrics in evaluating QAOA performance, based on collections of minima obtained from basin-hopping global optimization. Hence we establish expectation thresholds in elucidating useful solution probabilities from local minima, an approach that may provide significant gains in elucidating reasonable solution probabilities from local minima. Published by the American Physical Society 2024

arXiv:2401.04784•Physical Review A•Jun 3, 2024•15 citations

A Quantum Approximate Optimization Algorithm for Local Hamiltonian Problems

Ishaan Kannan, Robbie King, Leo Zhou

Local Hamiltonian Problems (LHPs) are important problems that are computationally QMA-complete and physically relevant for many-body quantum systems. Quantum MaxCut (QMC), which equates to finding ground states of the quantum Heisenberg model, is the canonical LHP for which various algorithms have been proposed, including semidefinite programs and variational quantum algorithms. We propose and analyze a quantum approximation algorithm which we call the Hamiltonian Quantum Approximate Optimization Algorithm (HamQAOA), which builds on the well-known scheme for combinatorial optimization and is suitable for implementations on near-term hardware. We establish rigorous performance guarantees of the HamQAOA for QMC on high-girth regular graphs, and our result provides bounds on the ground energy density for quantum Heisenberg spin glasses in the infinite size limit that improve with depth. Furthermore, we develop heuristic strategies with which to efficiently obtain good HamQAOA parameters. Through numerical simulations, we show that the HamQAOA empirically outperforms prior algorithms on a wide variety of QMC instances. In particular, our results indicate that the linear-depth HamQAOA can deterministically prepare exact ground states of 1-dimensional antiferromagnetic Heisenberg spin chains described by the Bethe ansatz, in contrast to the exponential depths required in previous protocols for preparing Bethe states.

arXiv:2412.09221•Dec 12, 2024•9 citations

Expectation values from the single-layer quantum approximate optimization algorithm on Ising problems

Asier Ozaeta, Wim van Dam, Peter L. McMahon

Abstract We report on the energy-expectation-value landscapes produced by the single-layer ( p = 1) quantum approximate optimization algorithm ( QAOA ) when being used to solve Ising problems. The landscapes are obtained using an analytical formula that we derive. The formula allows us to predict the landscape for any given Ising problem instance and consequently predict the optimal QAOA parameters for heuristically solving that instance using the single-layer QAOA . We have validated our analytical formula by showing that it accurately reproduces the landscapes published in recent experimental reports. We then applied our methods to address the question: how well is the single-layer QAOA able to solve large benchmark problem instances? We used our analytical formula to calculate the optimal energy-expectation values for benchmark M AX -C UT problems containing up to 7000 vertices and 41 459 edges. We also calculated the optimal energy expectations for general Ising problems with up to 100 000 vertices and 150 000 edges. Our results provide an estimate for how well the single-layer QAOA may work when run on a quantum computer with thousands of qubits. In addition to providing performance estimates when optimal angles are used, we are able to use our analytical results to investigate the difficulties one may encounter when running the QAOA in practice for different classes of Ising instances. We find that depending on the parameters of the Ising Hamiltonian, the expectation-value landscapes can be rather complex, with sharp features that necessitate highly accurate rotation gates in order for the QAOA to be run optimally on quantum hardware. We also present analytical results that explain some of the qualitative landscape features that are observed numerically.

arXiv:2012.03421•Quantum Science and Technology•Sep 7, 2022•57 citations

Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator

Guido Pagano, Aniruddha Bapat, Patrick Becker +13 more

Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.

arXiv:1906.02700•Proceedings of the National Academy of Sciences•Oct 6, 2020•304 citations

Quantum approximate optimization for hard problems in linear algebra

Ajinkya Borle, Vincent E. Elfving, Samuel J. Lomonaco

The quantum approximate optimization algorithm (QAOA) by Farhi et al. is a quantum computational framework for solving quantum or classical optimization tasks. Here, we explore using QAOA for binary linear least squares (BLLS); a problem that can serve as a building block of several other hard problems in linear algebra, such as the non-negative binary matrix factorization (NBMF) and other variants of the non-negative matrix factorization (NMF) problem. Most of the previous efforts in quantum computing for solving these problems were done using the quantum annealing paradigm. For the scope of this work, our experiments were done on noiseless quantum simulators, a simulator including a device-realistic noise-model, and two IBM Q 5-qubit machines. We highlight the possibilities of using QAOA and QAOA-like variational algorithms for solving such problems, where trial solutions can be obtained directly as samples, rather than being amplitude-encoded in the quantum wavefunction. Our numerics show that even for a small number of steps, simulated annealing can outperform QAOA for BLLS at a QAOA depth of p\leq3 p ≤ 3 for the probability of sampling the ground state. Finally, we point out some of the challenges involved in current-day experimental implementations of this technique on cloud-based quantum computers.

arXiv:2006.15438•SciPost Physics Core•Nov 30, 2021•39 citations

Sampling combinatorial energy landscapes by classical and quantum computation

Eric B. Jones

Combinatorial and, by extension, non-convex optimization problems are among the most difficult to solve computationally due to the inadequacy of local search methods alone to find global optima. The notion of an energy landscape provides a unified language to describe the origin of combinatorial complexity across a wide variety of fields including physics, materials science, and artificial intelligence. This thesis utilizes probabilistic techniques for efficiently sampling energy landscapes that rely on classical high-performance computers and near-term quantum computers. Such sampling techniques not only provide effective heuristics for solving combinatorial optimization problems, but also enable an explanation of physical phenomena that rely on features of the energy landscape other than the global optimum. Six use cases are considered that are of relevance to the design of future clean energy systems: i) a predictive theory of materials polymorphism based on the partitioning of the continuous energy landscape into structurally equivalent regions, ii) a theory of the structure of functional glasses based on thermally averaging structurally inequivalent regions, iii) solution of the minimum dominating set variant of the optimal phasor measurement unit placement problem on the power grid by quantum-annealing over a discrete, combinatorial solution landscape, iv) a reformulation and solution of the Markov decision process formalism underlying optimal control via quantum annealing, v) a prescription for the variational preparation of fractional quantum Hall states on a digital quantum computer that accommodates the size of the Hilbert space on quantum hardware while shifting the burden of variational minimization to classical, global optimization heuristics, and vi) the simulation of quantum cellular automata on a digital quantum computer and establishment thereby as primitives that could help design noise-resilient classically-parameterized unitary circuits such as those used in quantum machine learning. Through these domain examples, the outlook established herein is that efficient methods for exploring combinatorial energy landscapes, combined with resilience-minded near-term quantum algorithm construction and intelligent division of labor between quantum and classical resources, provide a promising path towards solving some of the most challenging problems in renewable energy science.

•Dec 31, 2019•0 citations
We show how the localization landscape, originally introduced to bound low-energy eigenstates of disordered wave media and many-body quantum systems, can form the basis for hardware-efficient quantum algorithms for solving binary optimization problems. Many binary optimization problems can be cast as finding low-energy eigenstates of Ising Hamiltonians. First, we apply specific perturbations to the Ising Hamiltonian such that the low-energy modes are bounded by the localization landscape. Next, we demonstrate how a variational method can be used to prepare and sample from the peaks of the localization landscape. Numerical simulations of problems of up to ten binary variables show that the localization landscape-based sampling can outperform quantum approximate optimization algorithm (QAOA) circuits of similar depth, as measured in terms of the probability of sampling the exact ground state.
Variational quantum algorithms (VQAs) have demonstrated considerable potential in solving NP-hard combinatorial problems in the contemporary noisy intermediate-scale quantum (NISQ) era. The quantum approximate optimization algorithm (QAOA) is one such algorithm, used in solving the maximum cut (Max-Cut) problem for a given graph by successive implementation of L quantum circuit layers within a corresponding Trotterized ansatz. The challenge of exploring the cost function of VQAs arising from an exponential proliferation of local minima with increasing circuit depth has been well documented. However, fewer studies have investigated the impact of circuit depth on QAOA performance in finding the correct Max-Cut solution. Here we employ basin-hopping global optimization methods to navigate the energy landscapes for QAOA ansätze for various graphs, and analyze QAOA performance in finding the correct Max-Cut solution. The structure of the solution space is also investigated using discrete path sampling to build databases of local minima and the transition states that connect them, providing insightful visualizations using disconnectivity graphs. We find that the corresponding landscapes generally have a single funnel organization, which makes it relatively straightforward to locate low-lying minima with good Max-Cut solution probabilities. In some cases below the adiabatic limit the second lowest local minimum may even yield a higher solution probability than the global minimum. This important observation has motivated us to develop broader metrics in evaluating QAOA performance, based on collections of minima obtained from basin-hopping global optimization. Hence we establish expectation thresholds in elucidating useful solution probabilities from local minima, an approach that may provide significant gains in elucidating reasonable solution probabilities from local minima. Published by the American Physical Society 2024
Local Hamiltonian Problems (LHPs) are important problems that are computationally QMA-complete and physically relevant for many-body quantum systems. Quantum MaxCut (QMC), which equates to finding ground states of the quantum Heisenberg model, is the canonical LHP for which various algorithms have been proposed, including semidefinite programs and variational quantum algorithms. We propose and analyze a quantum approximation algorithm which we call the Hamiltonian Quantum Approximate Optimization Algorithm (HamQAOA), which builds on the well-known scheme for combinatorial optimization and is suitable for implementations on near-term hardware. We establish rigorous performance guarantees of the HamQAOA for QMC on high-girth regular graphs, and our result provides bounds on the ground energy density for quantum Heisenberg spin glasses in the infinite size limit that improve with depth. Furthermore, we develop heuristic strategies with which to efficiently obtain good HamQAOA parameters. Through numerical simulations, we show that the HamQAOA empirically outperforms prior algorithms on a wide variety of QMC instances. In particular, our results indicate that the linear-depth HamQAOA can deterministically prepare exact ground states of 1-dimensional antiferromagnetic Heisenberg spin chains described by the Bethe ansatz, in contrast to the exponential depths required in previous protocols for preparing Bethe states.
Abstract We report on the energy-expectation-value landscapes produced by the single-layer ( p = 1) quantum approximate optimization algorithm ( QAOA ) when being used to solve Ising problems. The landscapes are obtained using an analytical formula that we derive. The formula allows us to predict the landscape for any given Ising problem instance and consequently predict the optimal QAOA parameters for heuristically solving that instance using the single-layer QAOA . We have validated our analytical formula by showing that it accurately reproduces the landscapes published in recent experimental reports. We then applied our methods to address the question: how well is the single-layer QAOA able to solve large benchmark problem instances? We used our analytical formula to calculate the optimal energy-expectation values for benchmark M AX -C UT problems containing up to 7000 vertices and 41 459 edges. We also calculated the optimal energy expectations for general Ising problems with up to 100 000 vertices and 150 000 edges. Our results provide an estimate for how well the single-layer QAOA may work when run on a quantum computer with thousands of qubits. In addition to providing performance estimates when optimal angles are used, we are able to use our analytical results to investigate the difficulties one may encounter when running the QAOA in practice for different classes of Ising instances. We find that depending on the parameters of the Ising Hamiltonian, the expectation-value landscapes can be rather complex, with sharp features that necessitate highly accurate rotation gates in order for the QAOA to be run optimally on quantum hardware. We also present analytical results that explain some of the qualitative landscape features that are observed numerically.
Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.
The quantum approximate optimization algorithm (QAOA) by Farhi et al. is a quantum computational framework for solving quantum or classical optimization tasks. Here, we explore using QAOA for binary linear least squares (BLLS); a problem that can serve as a building block of several other hard problems in linear algebra, such as the non-negative binary matrix factorization (NBMF) and other variants of the non-negative matrix factorization (NMF) problem. Most of the previous efforts in quantum computing for solving these problems were done using the quantum annealing paradigm. For the scope of this work, our experiments were done on noiseless quantum simulators, a simulator including a device-realistic noise-model, and two IBM Q 5-qubit machines. We highlight the possibilities of using QAOA and QAOA-like variational algorithms for solving such problems, where trial solutions can be obtained directly as samples, rather than being amplitude-encoded in the quantum wavefunction. Our numerics show that even for a small number of steps, simulated annealing can outperform QAOA for BLLS at a QAOA depth of p\leq3 p ≤ 3 for the probability of sampling the ground state. Finally, we point out some of the challenges involved in current-day experimental implementations of this technique on cloud-based quantum computers.
Combinatorial and, by extension, non-convex optimization problems are among the most difficult to solve computationally due to the inadequacy of local search methods alone to find global optima. The notion of an energy landscape provides a unified language to describe the origin of combinatorial complexity across a wide variety of fields including physics, materials science, and artificial intelligence. This thesis utilizes probabilistic techniques for efficiently sampling energy landscapes that rely on classical high-performance computers and near-term quantum computers. Such sampling techniques not only provide effective heuristics for solving combinatorial optimization problems, but also enable an explanation of physical phenomena that rely on features of the energy landscape other than the global optimum. Six use cases are considered that are of relevance to the design of future clean energy systems: i) a predictive theory of materials polymorphism based on the partitioning of the continuous energy landscape into structurally equivalent regions, ii) a theory of the structure of functional glasses based on thermally averaging structurally inequivalent regions, iii) solution of the minimum dominating set variant of the optimal phasor measurement unit placement problem on the power grid by quantum-annealing over a discrete, combinatorial solution landscape, iv) a reformulation and solution of the Markov decision process formalism underlying optimal control via quantum annealing, v) a prescription for the variational preparation of fractional quantum Hall states on a digital quantum computer that accommodates the size of the Hilbert space on quantum hardware while shifting the burden of variational minimization to classical, global optimization heuristics, and vi) the simulation of quantum cellular automata on a digital quantum computer and establishment thereby as primitives that could help design noise-resilient classically-parameterized unitary circuits such as those used in quantum machine learning. Through these domain examples, the outlook established herein is that efficient methods for exploring combinatorial energy landscapes, combined with resilience-minded near-term quantum algorithm construction and intelligent division of labor between quantum and classical resources, provide a promising path towards solving some of the most challenging problems in renewable energy science.