This paper proposes a novel combination of constraint encoding methods for the Quantum Approximate Optimization Ansatz (QAOA). Real-world optimization problems typically consist of multiple types of constraints. To solve these optimization problems with quantum methods, normally, all constraints are added as quadratic penalty terms to the objective, which expands the search space and increases problem complexity. This work proposes a general workflow that extracts and encodes specific constraints directly into the circuit of QAOA: One-hot constraints are enforced through$X Y$-mixers that restrict the search space to the feasible sub-space naturally. Inequality constraints are implemented through oracle-based Indicator Functions (IF). This paper focuses on the numerical benchmarks of the combined approach for solving the Multi-Knapsack (MKS) and the Prosumer Problem (PP), a modification of the MKS in the domain of electricity optimization. To this end, we introduce computational techniques that efficiently simulate the two presented constraint architectures. Since$X Y$-mixers restrict the search space, specific state vector entries are always zero and can be omitted from the simulation, saving valuable memory and computing resources. We benchmark the combined method against the established QUBO formulation, yielding a better solution quality and probability of sampling the optimal solution. Despite more complex circuits, the time-to-solution is more than an order of magnitude faster compared to the baseline methods and exhibits more favorable scaling properties.
This paper proposes a novel combination of constraint encoding methods for the Quantum Approximate Optimization Ansatz (QAOA). Real-world optimization problems typically consist of multiple types of constraints. To solve these optimization problems with quantum methods, normally, all constraints are added as quadratic penalty terms to the objective, which expands the search space and increases problem complexity. This work proposes a general workflow that extracts and encodes specific constraints directly into the circuit of QAOA: One-hot constraints are enforced throughXY-mixers that restrict the search space to the feasible sub-space naturally. Inequality constraints are implemented through oracle-based Indicator Functions (IF). This paper focuses on the numerical benchmarks of the combined approach for solving the Multi-Knapsack (MKS) and the Prosumer Problem (PP), a modification of the MKS in the domain of electricity optimization. To this end, we introduce computational techniques that efficiently simulate the two presented constraint architectures. SinceXY-mixers restrict the search space, specific state vector entries are always zero and can be omitted from the simulation, saving valuable memory and computing resources. We benchmark the combined method against the established QUBO formulation, yielding a better solution quality and probability of sampling the optimal solution. Despite more complex circuits, the time-to-solution is more than an order of magnitude faster compared to the baseline methods and exhibits more favorable scaling properties.
Traditional methods for handling (inequality) constraints in the quantum approximate optimization (QAOA) typically rely on penalty terms and slack variables, which increase problem complexity and expand the search space. More sophisticated mixer-based QAOA variants restrict the search within the feasible assignments but often suffer from prohibitive circuit complexity. This paper presents a penalty-free formalism for incorporating inequality constraints into the cost function of QAOA using an oracle-based subroutine that evaluates constraint satisfaction in an additional register, subsequently called indicator function QAOA (IF-QAOA). Applied to the knapsack problem, we demonstrate in numerical simulations the superior performance of IF-QAOA over conventional penalty-based approaches. Using advanced QAOA simulation techniques, we find that IF-QAOA achieves significantly higher solution quality and a faster time to solution in 82% of our benchmark cases, even though circuit depth is approximately three times larger. Analysis of the scaling behavior shows favorable scaling of IF-QAOA compared to penalty-based methods. Also, benchmarks against the recently developed quantum tree generator QAOA for knapsack problems (P. Christiansen , ) demonstrated higher solution quality for circuits of similar depth. Additionally, this paper introduces a method for approximating the indicator function when the number of ancillary qubits is limited or the constraint function is noninteger. With a specialized simulation algorithm based on projective measurements, we empirically demonstrate that this formalism can encode general inequality constraints using a fixed number of ancillary qubits.
Constrained combinatorial optimization problems are challenging for quantum computing, particularly at utility-relevant scales and on near-term hardware. At the same time, these problems are of practical significance in industry; for example, the Unit Commitment (UC) problem in energy systems involves complex operational constraints. To address this challenge, we apply copula-QAOA (cop-QAOA), a hardware-efficient approach for constrained optimization to a single-period UC that can be reduced to a one-dimensional knapsack. Cop-QAOA biases the quantum state toward feasible solutions using constant-depth mixers and appropriately biased initial states. We implement our benchmark on problem instances that are confirmed to be hard for classical solvers such as Gurobi. Our results show that cop-QAOA often finds solutions better than a lazy greedy baseline and very close to, and in some instances surpasses, those obtained by Gurobi, with only a few QAOA rounds. This work presents the largest successful demonstration of the knapsack problem on IBM Quantum hardware using up to 150 qubits, and more generally, the largest demonstration of constrained combinatorial optimization where constraints are enforced via shallow mixers.
Quantum Approximate Optimization Algorithm, further generalized as Quantum Alternating Operator Ansatz (QAOA), is a family of algorithms for combinatorial optimization problems. It is a leading candidate to run on emerging universal quantum computers to gain insight into quantum heuristics. In constrained optimization, penalties are often introduced so that the ground state of the cost Hamiltonian encodes the solution (a standard practice in quantum annealing). An alternative is to choose a mixing Hamiltonian such that the constraint corresponds to a constant of motion and the quantum evolution stays in the feasible subspace. Better performance of the algorithm is speculated due to a much smaller search space. We consider problems with a constant Hamming weight as the constraint. We also compare different methods of generating the generalized W-state, which serves as a natural initial state for the Hamming-weight constraint. Using graph-coloring as an example, we compare the performance of using XY model as a mixer that preserves the Hamming weight with the performance of adding a penalty term in the cost Hamiltonian.
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.
Recently, Hadfield et al. proposed the quantum alternating operator ansatz algorithm (QAOA+), an extension of the quantum approximate optimization algorithm (QAOA), to solve constrained combinatorial optimization problems (CCOPs). Compared with QAOA, QAOA+ enables the search for optimal solutions within a feasible solution space by encoding problem constraints into the mixer Hamiltonian, thereby reducing the search space and eliminating the possibility of yielding infeasible solutions. However, QAOA+ may incur high overall gate costs when the mixer is applied to all qubits in each layer, and each mixer is costly to implement. To address this challenge, an adaptive mixer allocation strategy is tailored for QAOA+. The resulting algorithm, which integrates this strategy into the original QAOA+ framework, is referred to as AMA-QAOA+. Unlike QAOA+, AMA-QAOA+ adaptively applies the mixer to a subset of qubits in each layer of the mixer unitary operator based on an evaluation function. The performance of AMA-QAOA+ is evaluated on the maximum independent set problem. Numerical simulation results show that, under the same number of optimization runs, AMA-QAOA+ achieves better solution quality than QAOA+, with the optimal approximation ratio improved by 5.30% on ER random graphs and 5.41% on 3-regular graphs. Moreover, AMA-QAOA+ significantly reduces the CNOT gate consumption, requiring only 15.30% and 25.18% of the CNOT gates used by QAOA+ on ER and 3-regular random graphs, respectively. These results demonstrate that AMA-QAOA+ enhances solution quality and computational efficiency, enabling the design of more compact and resource-efficient quantum circuits.
This dissertation addresses fundamental challenges in solving constrained combinatorial optimization problems using hybrid quantum-classical computing approaches. Quantum computing shows promise for tackling computationally intractable problems, current approaches face significant limitations. The path forward in computing involves combining quantum and classical computing approaches. Quantum processing units (QPUs) will play a key role in accelerating algorithms in optimization, simulation, and machine learning applications beyond what classical computers can achieve on their own, similar to how graphical processing units (GPUs) have become integral to general-purpose computing. The current generation of quantum devices is limited by noise and circuit depth constraints, making it challenging to gain practical utility. Hybrid quantum-classical approaches, which combine quantum computing resources with classical computing resources, are essential for addressing these limitations on near-term devices. In the area of combinatorial optimization, current practical state-of-the-art hybrid approaches are variational in nature, relying on parameterized quantum circuits to encode solutions and classical optimization techniques to find optimal parameters. While the ultimate goal of solving computationally intractable problems is to find provably optimal solutions, practical constraints of real-world scenarios often necessitate focusing on efficiently obtaining high-quality, near-optimal solutions. The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical approach for tackling these challenging problems that are encoded using quadratic and higher-order unconstrained binary optimization problems (QUBO and HUBO). QAOA alternates between two operators: a problem-specific cost Hamiltonian that encodes the optimization objective, and a mixer Hamiltonian that explores the solution space. The algorithm's parameters are iteratively optimized using classical methods to maximize the probability of sampling high-quality solutions. However, these methods often struggle with solution feasibility, especially for problems where the solutions must satisfy specific constraints. Penalty-based encodings require careful parameter tuning and risk producing infeasible solutions, while feasibility-preserving methods demand deeper quantum circuits that are challenging to implement on near-term quantum devices. In this dissertation, we present novel strategies that reduce or omit dependency on penalty parameters while maintaining solution quality, effectively capturing both optimal and near-optimal solutions, and balancing the trade-offs between circuit depth and solution feasibility. We present SCOOP, a novel QAOA-based framework for solving constrained optimization problems. SCOOP transforms a constrained problem into an unconstrained counterpart, forming SCOOP problem twins. QAOA operates on the unconstrained twin to identify potential optimal and near-optimal solutions. Effective classical post-processing reduces the solution set to the constrained problem space. Our SCOOP approach is solution-enhanced, objective-function-compatible, and scalable. We demonstrate the effectiveness of the SCOOP framework on selected NP-hard problems, some of which can be encoded quadratically (such as Minimum Vertex Cover and Maximum Independent Set), and some that can be encoded using higher-order terms (such as Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover). We also apply our framework to constrained combinatorial optimization problems that can be solved in polynomial time, such as Minimum Edge Cover and Maximum Matching. Experimental results on full statevector simulators and tensor network simulators show that SCOOP significantly improves the probability of finding high-quality feasible solutions across various problem classes, on problems that can be encoded quadratically as well as problems that can be encoded using higher-order terms. We also demonstrate the effectiveness of SCOOP on real quantum hardware, specifically IBM Quantum Heron R2 processors with 156 qubits, showing that SCOOP can be applied to practical problems with current quantum hardware limitations. This work makes significant contributions toward achieving quantum utility by enabling systematic investigation of constrained optimization problems on quantum devices. While current quantum computing research primarily focuses on unconstrained problems like MaxCut, real-world applications typically involve constraints. SCOOP provides a scalable framework for encoding constrained problems, extending quantum computing's practical utility beyond simple unconstrained cases. By eliminating dependency on penalty parameters and providing natural problem formulations, SCOOP makes it feasible to explore quantum solutions for constrained problems where classical exact methods become intractable. This capability is crucial for identifying promising avenues for demonstrating quantum utility across diverse constrained optimization problems, advancing the practical applicability of quantum computing approaches.