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

International Conference on Information Technology: New Generations

Some Investigations for Solving Constrained Optimization Problems using Adiabatic Quantum Computation

Ashish Mani, C. Patvardhan

Published Apr 1, 2011• 0 citations
Publisher

Abstract

Adiabatic Quantum Computation has emerged as a new approach for designing quantum algorithms, which is equivalent to the circuit model but appears to be more robust and suffers from less number of bottlenecks than it. Some investigations have been undertaken in this paper for solving constrained optimization problems using Adiabatic Quantum Computation, as there is no reported approach yet for solving such problems using Quantum Algorithms.

DOI
10.1109/itng.2011.218

Related papers

How powerful is adiabatic quantum computation?

W. van Dam, M. Mosca, U. Vazirani

The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.

arXiv:quant-ph/0206003•Annual Symposium on Foundations of Computer Science•Jan 1, 2001•175 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

Adiabatic Quantum Computing and Global Solution of NP-Hard QUBO Problems: A General Approach

Sanjay Sharma, Ravi Kumar

QUBO problems are NP-hard and have wide applications in optimization, including finance, logistics, machine learning, and combinatorial problems. However, classical algorithms employed for solving them can often get stuck in local minima. This paper presents an Adiabatic Quantum Computing (AQC) approach towards finding an optimal solution for QUBO problems. The QUBO problem has been first encoded into Hamiltonians. The adiabatic theorem has been used to achieve success of an AQC solution with a rate which is found to be dependent on relative gap between the ground state and first exited state of the Hamiltonian.

IEEE International Conference on Interdisciplinary Approaches in Technology and Management for Social Innovation (IATMSI)•Mar 12, 2026•0 citations

Lagrangian duality in quantum optimization: Overcoming QUBO limitations for constrained problems

Einar Gabbassov, Gili Rosenberg, Artur Scherer

We propose an approach to solving constrained combinatorial optimization problems based on embedding the concept of Lagrangian duality into the framework of adiabatic quantum computation. Within the setting of circuit-model fault-tolerant quantum computation, we demonstrate that this approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width in contrast with the prevalent approach of solving constrained problems via reformulations based on the quadratic unconstrained binary optimization (QUBO) framework. In this study, we include a detailed review of the limitations encountered when using QUBO for constrained optimization. We show that the proposed method overcomes these limitations by encoding the optimal solution at an energetically elevated level of a simpler problem Hamiltonian, which results in substantially more resource-efficient quantum circuits. We consolidate our strategy with a detailed analysis on how the concepts of Lagrangian duality such as duality gap and complementary slackness relate to the success probability of sampling the optimal solution. Our findings are illustrated by benchmarking the Lagrangian dual approach against the QUBO approach using the NP-complete binary knapsack problem.

arXiv:2310.04542•Physical Review Research•May 23, 2025•5 citations

Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation

Dorit Aharonov, Wim van Dam, Julia Kempe +3 more

The model of adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its exact computational power has been unknown. We settle this question and describe an efficient adiabatic simulation of any given quantum algorithm. This implies that the adiabatic computation model and the standard quantum circuit model are polynomially equivalent. We also describe an extension of this result with implications to physical implementations of adiabatic computation. We believe that our result highlights the potential importance of the adiabatic computation model in the design of quantum algorithms and in their experimental realization.

Annual Symposium on Foundations of Computer Science•Dec 23, 2004•159 citations

Survey of adiabatic quantum optimization algorithms

Yingyi Zhang

Adiabatic quantum optimization was first proposed in 2001,which was attended to solve the NPC combinatorial optimization problems,and soon became one of the hot topics in quantum computation.This survey reviews the progress in the field of adiabatic quantum optimization in the past decade,and summarizes the key methods and techniques used in the studies of adiabatic quantum optimization algorithms.Finally,this survey is concluded by predicting the future of the field.

Computer Engineering and Science•Jan 1, 2015•0 citations
Adiabatic Quantum Computation has emerged as a new approach for designing quantum algorithms, which is equivalent to the circuit model but appears to be more robust and suffers from less number of bottlenecks than it. Some investigations have been undertaken in this paper for solving constrained optimization problems using Adiabatic Quantum Computation, as there is no reported approach yet for solving such problems using Quantum Algorithms.
The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.
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.
QUBO problems are NP-hard and have wide applications in optimization, including finance, logistics, machine learning, and combinatorial problems. However, classical algorithms employed for solving them can often get stuck in local minima. This paper presents an Adiabatic Quantum Computing (AQC) approach towards finding an optimal solution for QUBO problems. The QUBO problem has been first encoded into Hamiltonians. The adiabatic theorem has been used to achieve success of an AQC solution with a rate which is found to be dependent on relative gap between the ground state and first exited state of the Hamiltonian.
We propose an approach to solving constrained combinatorial optimization problems based on embedding the concept of Lagrangian duality into the framework of adiabatic quantum computation. Within the setting of circuit-model fault-tolerant quantum computation, we demonstrate that this approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width in contrast with the prevalent approach of solving constrained problems via reformulations based on the quadratic unconstrained binary optimization (QUBO) framework. In this study, we include a detailed review of the limitations encountered when using QUBO for constrained optimization. We show that the proposed method overcomes these limitations by encoding the optimal solution at an energetically elevated level of a simpler problem Hamiltonian, which results in substantially more resource-efficient quantum circuits. We consolidate our strategy with a detailed analysis on how the concepts of Lagrangian duality such as duality gap and complementary slackness relate to the success probability of sampling the optimal solution. Our findings are illustrated by benchmarking the Lagrangian dual approach against the QUBO approach using the NP-complete binary knapsack problem.
The model of adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its exact computational power has been unknown. We settle this question and describe an efficient adiabatic simulation of any given quantum algorithm. This implies that the adiabatic computation model and the standard quantum circuit model are polynomially equivalent. We also describe an extension of this result with implications to physical implementations of adiabatic computation. We believe that our result highlights the potential importance of the adiabatic computation model in the design of quantum algorithms and in their experimental realization.