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:2304.06915

Quasi-binary encoding based quantum alternating operator ansatz

Bingren Chen, Hanqing Wu, Haomu Yuan, Lei Wu, Xin Li

Published Apr 14, 2023• 0 citations
arXivHTMLPDF

Abstract

This paper proposes a quasi-binary encoding based algorithm for solving a specific quadratic optimization models with discrete variables, in the quantum approximate optimization algorithm (QAOA) framework. The quadratic optimization model has three constraints: 1. Discrete constraint, the variables are required to be integers. 2. Bound constraint, each variable is required to be greater than or equal to an integer and less than or equal to another integer. 3. Sum constraint, the sum of all variables should be a given integer. To solve this optimization model, we use quasi-binary encoding to encode the variables. For an integer variable with upper bound $U_i$ and lower bound $L_i$, this encoding method can use at most $2\log_2 (U_i-L_i+1)$ qubits to encode the variable. Moreover, we design a mixing operator specifically for this encoding to satisfy the hard constraint model. In the hard constraint model, the quantum state always satisfies the constraints during the evolution, and no penalty term is needed in the objective function. In other parts of the QAOA framework, we also incorporate ideas such as CVaR-QAOA and parameter scheduling methods into our QAOA algorithm. In the financial field, by introducing precision, portfolio optimization problems can be reduced to the above model. We will use portfolio optimization cases for numerical simulation. We design an iterative method to solve the problem of coarse precision caused by insufficient qubits of the simulators or quantum computers. This iterative method can refine the precision by multiple few-qubit experiments.

DOI
10.48550/arxiv.2304.06915

Related papers

An Efficient Hybrid Classical Quantum Algorithm for Mixed-Integer Constrained Optimization

Amit Surana

Widely used quantum optimization algorithms such as quantum annealing and quantum approximate optimization algorithm (QAOA) for quadratically unconstrained binary optimization (QUBO) problems cannot systematically and efficiently handle constraints and mixed discrete and continuous decision variables. To address this, we present a novel hybrid classicalquantum approach which combines classical alternating direction method of multipliers (ADMM) with QAOA. Compared to conventional penalty-based method, this approach avoids quantization of continuous variables, eliminates the need for additional qubits to capture constraints on a quantum device and leads to reduced QAOA circuit depth suitable for near term implementation. We illustrate the efficacy of our approach on several constrained mixed integer optimization problems.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems

Nicolas P. D. Sawaya, Albert T. Schmitz, Stuart Hadfield

Challenging combinatorial optimization problems are ubiquitous in science and engineering. Several quantum methods for optimization have recently been developed, in different settings including both exact and approximate solvers. Addressing this field of research, this manuscript has three distinct purposes. First, we present an intuitive method for synthesizing and analyzing discrete ( i . e . , integer-based) optimization problems, wherein the problem and corresponding algorithmic primitives are expressed using a discrete quantum intermediate representation (DQIR) that is encoding-independent. This compact representation often allows for more efficient problem compilation, automated analyses of different encoding choices, easier interpretability, more complex runtime procedures, and richer programmability, as compared to previous approaches, which we demonstrate with a number of examples. Second, we perform numerical studies comparing several qubit encodings; the results exhibit a number of preliminary trends that help guide the choice of encoding for a particular set of hardware and a particular problem and algorithm. Our study includes problems related to graph coloring, the traveling salesperson problem, factory/machine scheduling, financial portfolio rebalancing, and integer linear programming. Third, we design low-depth graph-derived partial mixers (GDPMs) up to 16-level quantum variables, demonstrating that compact (binary) encodings are more amenable to QAOA than previously understood. We expect this toolkit of programming abstractions and low-level building blocks to aid in designing quantum algorithms for discrete combinatorial problems.

arXiv:2203.14432•Quantum•Sep 14, 2023•14 citations

Quantum optimisation algorithms and their applications

Haomu Yuan

This thesis is devoted to four modern quantum optimisation algorithms and their applications. In the first chapter, we provide a complete Quantum Approximate Optimisation Algorithm (QAOA) pipeline for the discrete global minimum-variance portfolio (DGMVP) problem. We introduce an ansatz with efficient initial-state preparation, new hard mixing operators satisfying the constraints of the DGMVP problem, and scalable cost operators utilising binary encoding of the qubits. Benchmarking the method with the most effective optimisation strategies---dual annealing and unfrozen layerwise optimisation---indicates a scaling advantage over classical methods in finding the global optimum of the DGMVP problem. In the second chapter, we show an end-to-end quantum/quantum-inspired Goemans-Williamson semidefinite programming (SDP) method for relaxing Quadratic Unconstrained Binary Optimisation (QUBO) problems and extracting their rounding energy. Our method identifies a class of QUBO instances that is effectively solvable in polylogarithmic time relative to the problem dimension, under the assumptions of Pauli sparsification of the QUBO cost matrix, reducibility of the diagonal constraints, and efficient evaluation of the corresponding Gibbs-state expectation values. Further, we identify the commuting 1D Hamiltonian and the Kronecker graph as practically important instances. Our numerical experiments show that our method solves the SDP and QUBO with up to $2^{50}$ variables for 1D Hamiltonian instances and achieves results competitive with the best classical solver for Kronecker graphs, giving strong evidence of the power of our algorithm. In the third chapter, we improve the current QAOA method with an iterative warm-start initial-state preparation method. We implement the $t$-th order statistic state as the warm-start initial state generated from each QAOA optimisation loop. We achieve an improved approximation ratio when solving the 3-regular MaxCut problem, and find that the worst-case approximation ratio converges to that of the best classical algorithm for $p=1$ QAOA. Additionally, our method achieves more favourable scaling than standalone QAOA, single-string warm-started QAOA, and a classical constrained-sampling approach when solving the DGMVP problem. In the fourth chapter, we provide a hard-constrained Grover adaptive search (GAS) method for fixed-sum quadratic binary optimisation problems, and an extension of the alternating direction method of multipliers (ADMM) framework for fixed-sum quartic binary optimisation. Our method guarantees at least a quadratic speed-up over the classical method, and exponentially reduces the gate count for solving fixed-sum binary optimisation when compared with the soft-constrained GAS in the fault-tolerant quantum computing regime. In summary, our contributions include efficient algorithms and novel frameworks that substantially improve performance and broaden the applicability of these quantum optimisation methods. The proposed methods exhibit favourable scaling behaviour and indicate potential quantum advantages in solving challenging optimisation problems, thereby motivating further research at the interface of quantum computing and optimisation.

•Jan 22, 2026•0 citations

XY mixers: Analytical and numerical results for the quantum alternating operator ansatz

Zhihui Wang, Nicholas C. Rubin, Jason Dominy +1 more

The quantum alternating operator ansatz (QAOA) is a promising gate-model metaheuristic for combinatorial optimization. Applying the algorithm to problems with constraints presents an implementation challenge for near-term quantum resources. This paper explores strategies for enforcing hard constraints by using $XY$ Hamiltonians as mixing operators (mixers). Despite the complexity of simulating the $XY$ model, we demonstrate that, for an integer variable admitting $\ensuremath{\kappa}$ discrete values represented through one-hot encoding, certain classes of the mixer Hamiltonian can be implemented without Trotter error in depth $O(\ensuremath{\kappa})$. We also specify general strategies for implementing QAOA circuits on all-to-all connected hardware graphs and linearly connected hardware graphs inspired by fermionic simulation techniques. Performance is validated on graph-coloring problems that are known to be challenging for a given classical algorithm. The general strategy of using $XY$ mixers is borne out numerically, demonstrating a significant improvement over the general $X$ mixer, and moreover the generalized $W$ state yields better performance than easier-to-generate classical initial states when $XY$ mixers are used.

arXiv:1904.09314•Physical Review A•Jan 14, 2020•189 citations

Encoding Matters: Benchmarking Binary and D-ary Representations for Quantum Combinatorial Optimization

Shashank Sanjay Bhat, Peiyong Wang, Joseph West +1 more

Combinatorial optimization problems are typically formulated using Quadratic Unconstrained Binary Optimization (QUBO), where constraints are enforced through penalty terms that introduce auxiliary variables and rapidly increase Hamiltonian complexity, limiting scalability on near term quantum devices. In this work, we systematically study Quadratic Unconstrained D-ary Optimization (QUDO) as an alternative formulation in which decision variables are encoded directly in higher dimensional Hilbert spaces. We demonstrate that QUDO naturally captures structural constraints across a range of problem classes, including the Traveling Salesman Problem, two variants of the Vehicle Routing Problem, graph coloring, job scheduling, and Max-K-Cut, without the need for extensive penalty constructions. Using a qudit-level implementation of the Quantum Approximate Optimization Algorithm (qudit QAOA), we benchmark these formulations against their binary QUBO counterparts and exact classical solutions. Our study show consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths, highlighting QUDO as a scalable and expressive representation for quantum combinatorial optimization.

quant-pharXiv:2602.07357•Feb 10, 2026•0 citations

Resource-efficient QUBO formulations for the Knapsack and Bin Packing problem

Pim van den Heuvel

Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.

•Jan 1, 2025•0 citations
This paper proposes a quasi-binary encoding based algorithm for solving a specific quadratic optimization models with discrete variables, in the quantum approximate optimization algorithm (QAOA) framework. The quadratic optimization model has three constraints: 1. Discrete constraint, the variables are required to be integers. 2. Bound constraint, each variable is required to be greater than or equal to an integer and less than or equal to another integer. 3. Sum constraint, the sum of all variables should be a given integer. To solve this optimization model, we use quasi-binary encoding to encode the variables. For an integer variable with upper bound UiU_iUi​ and lower bound LiL_iLi​, this encoding method can use at most 2log⁡2(Ui−Li+1)2\log_2 (U_i-L_i+1)2log2​(Ui​−Li​+1) qubits to encode the variable. Moreover, we design a mixing operator specifically for this encoding to satisfy the hard constraint model. In the hard constraint model, the quantum state always satisfies the constraints during the evolution, and no penalty term is needed in the objective function. In other parts of the QAOA framework, we also incorporate ideas such as CVaR-QAOA and parameter scheduling methods into our QAOA algorithm. In the financial field, by introducing precision, portfolio optimization problems can be reduced to the above model. We will use portfolio optimization cases for numerical simulation. We design an iterative method to solve the problem of coarse precision caused by insufficient qubits of the simulators or quantum computers. This iterative method can refine the precision by multiple few-qubit experiments.
Widely used quantum optimization algorithms such as quantum annealing and quantum approximate optimization algorithm (QAOA) for quadratically unconstrained binary optimization (QUBO) problems cannot systematically and efficiently handle constraints and mixed discrete and continuous decision variables. To address this, we present a novel hybrid classicalquantum approach which combines classical alternating direction method of multipliers (ADMM) with QAOA. Compared to conventional penalty-based method, this approach avoids quantization of continuous variables, eliminates the need for additional qubits to capture constraints on a quantum device and leads to reduced QAOA circuit depth suitable for near term implementation. We illustrate the efficacy of our approach on several constrained mixed integer optimization problems.
Challenging combinatorial optimization problems are ubiquitous in science and engineering. Several quantum methods for optimization have recently been developed, in different settings including both exact and approximate solvers. Addressing this field of research, this manuscript has three distinct purposes. First, we present an intuitive method for synthesizing and analyzing discrete ( i . e . , integer-based) optimization problems, wherein the problem and corresponding algorithmic primitives are expressed using a discrete quantum intermediate representation (DQIR) that is encoding-independent. This compact representation often allows for more efficient problem compilation, automated analyses of different encoding choices, easier interpretability, more complex runtime procedures, and richer programmability, as compared to previous approaches, which we demonstrate with a number of examples. Second, we perform numerical studies comparing several qubit encodings; the results exhibit a number of preliminary trends that help guide the choice of encoding for a particular set of hardware and a particular problem and algorithm. Our study includes problems related to graph coloring, the traveling salesperson problem, factory/machine scheduling, financial portfolio rebalancing, and integer linear programming. Third, we design low-depth graph-derived partial mixers (GDPMs) up to 16-level quantum variables, demonstrating that compact (binary) encodings are more amenable to QAOA than previously understood. We expect this toolkit of programming abstractions and low-level building blocks to aid in designing quantum algorithms for discrete combinatorial problems.
This thesis is devoted to four modern quantum optimisation algorithms and their applications. In the first chapter, we provide a complete Quantum Approximate Optimisation Algorithm (QAOA) pipeline for the discrete global minimum-variance portfolio (DGMVP) problem. We introduce an ansatz with efficient initial-state preparation, new hard mixing operators satisfying the constraints of the DGMVP problem, and scalable cost operators utilising binary encoding of the qubits. Benchmarking the method with the most effective optimisation strategies---dual annealing and unfrozen layerwise optimisation---indicates a scaling advantage over classical methods in finding the global optimum of the DGMVP problem. In the second chapter, we show an end-to-end quantum/quantum-inspired Goemans-Williamson semidefinite programming (SDP) method for relaxing Quadratic Unconstrained Binary Optimisation (QUBO) problems and extracting their rounding energy. Our method identifies a class of QUBO instances that is effectively solvable in polylogarithmic time relative to the problem dimension, under the assumptions of Pauli sparsification of the QUBO cost matrix, reducibility of the diagonal constraints, and efficient evaluation of the corresponding Gibbs-state expectation values. Further, we identify the commuting 1D Hamiltonian and the Kronecker graph as practically important instances. Our numerical experiments show that our method solves the SDP and QUBO with up to 2502^{50}250 variables for 1D Hamiltonian instances and achieves results competitive with the best classical solver for Kronecker graphs, giving strong evidence of the power of our algorithm. In the third chapter, we improve the current QAOA method with an iterative warm-start initial-state preparation method. We implement the ttt-th order statistic state as the warm-start initial state generated from each QAOA optimisation loop. We achieve an improved approximation ratio when solving the 3-regular MaxCut problem, and find that the worst-case approximation ratio converges to that of the best classical algorithm for p=1p=1p=1 QAOA. Additionally, our method achieves more favourable scaling than standalone QAOA, single-string warm-started QAOA, and a classical constrained-sampling approach when solving the DGMVP problem. In the fourth chapter, we provide a hard-constrained Grover adaptive search (GAS) method for fixed-sum quadratic binary optimisation problems, and an extension of the alternating direction method of multipliers (ADMM) framework for fixed-sum quartic binary optimisation. Our method guarantees at least a quadratic speed-up over the classical method, and exponentially reduces the gate count for solving fixed-sum binary optimisation when compared with the soft-constrained GAS in the fault-tolerant quantum computing regime. In summary, our contributions include efficient algorithms and novel frameworks that substantially improve performance and broaden the applicability of these quantum optimisation methods. The proposed methods exhibit favourable scaling behaviour and indicate potential quantum advantages in solving challenging optimisation problems, thereby motivating further research at the interface of quantum computing and optimisation.
The quantum alternating operator ansatz (QAOA) is a promising gate-model metaheuristic for combinatorial optimization. Applying the algorithm to problems with constraints presents an implementation challenge for near-term quantum resources. This paper explores strategies for enforcing hard constraints by using XYXYXY Hamiltonians as mixing operators (mixers). Despite the complexity of simulating the XYXYXY model, we demonstrate that, for an integer variable admitting $\ensuremath{\kappa}$ discrete values represented through one-hot encoding, certain classes of the mixer Hamiltonian can be implemented without Trotter error in depth $O(\ensuremath{\kappa})$. We also specify general strategies for implementing QAOA circuits on all-to-all connected hardware graphs and linearly connected hardware graphs inspired by fermionic simulation techniques. Performance is validated on graph-coloring problems that are known to be challenging for a given classical algorithm. The general strategy of using XYXYXY mixers is borne out numerically, demonstrating a significant improvement over the general XXX mixer, and moreover the generalized WWW state yields better performance than easier-to-generate classical initial states when XYXYXY mixers are used.
Combinatorial optimization problems are typically formulated using Quadratic Unconstrained Binary Optimization (QUBO), where constraints are enforced through penalty terms that introduce auxiliary variables and rapidly increase Hamiltonian complexity, limiting scalability on near term quantum devices. In this work, we systematically study Quadratic Unconstrained D-ary Optimization (QUDO) as an alternative formulation in which decision variables are encoded directly in higher dimensional Hilbert spaces. We demonstrate that QUDO naturally captures structural constraints across a range of problem classes, including the Traveling Salesman Problem, two variants of the Vehicle Routing Problem, graph coloring, job scheduling, and Max-K-Cut, without the need for extensive penalty constructions. Using a qudit-level implementation of the Quantum Approximate Optimization Algorithm (qudit QAOA), we benchmark these formulations against their binary QUBO counterparts and exact classical solutions. Our study show consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths, highlighting QUDO as a scalable and expressive representation for quantum combinatorial optimization.
Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.