When tackling binary optimization problems using quantum algorithms, the conventional Ising representation and Quantum Approximate Optimization Algorithm (QAOA) encounter difficulties in efficiently handling errors for large-scale problems involving multiple constraints. To address these challenges, this paper presents a hybrid framework that combines the use of standard Ising Hamiltonians to solve a subset of the constraints, while employing non-Ising formulations to represent and address the remaining constraints. The resolution of these non-Ising constraints is achieved through either penalty dephasing or the quantum Zeno effect. This innovative approach leads to a collection of quantum circuits with adaptable structures, depending on the chosen representation for each constraint. Furthermore, this paper introduces a novel technique that utilizes the quantum Zeno effect by frequently measuring the constraint flag, enabling the resolution of any optimization constraint. Theoretical properties of these algorithms are discussed, and their performance in addressing practical aircraft loading problems is highly promising, showcasing significant potential for a wide range of industrial applications.
When tackling binary optimization problems using quantum algorithms, the conventional Ising representation and Quantum Approximate Optimization Algorithm (QAOA) encounter difficulties in efficiently handling errors for large-scale problems involving multiple constraints. To address these challenges, this paper presents a hybrid framework that combines the use of standard Ising Hamiltonians to solve a subset of the constraints, while employing non-Ising formulations to represent and address the remaining constraints. The resolution of these non-Ising constraints is achieved through either penalty dephasing or the quantum Zeno effect. This innovative approach leads to a collection of quantum circuits with adaptable structures, depending on the chosen representation for each constraint. Furthermore, this paper introduces a novel technique that utilizes the quantum Zeno effect by frequently measuring the constraint flag, enabling the resolution of any optimization constraint. Theoretical properties of these algorithms are discussed, and their performance in addressing practical aircraft loading problems is highly promising, showcasing significant potential for a wide range of industrial applications.
The Quantum Approximate Optimization Algorithm (QAOA) represents a significant opportunity for practical quantum computing applications, particularly in the era before error correction is fully realized. This algorithm is especially relevant for addressing constraint satisfaction problems (CSPs), which are critical in various fields such as supply chain management, energy distribution, and financial modeling. In our study, we conduct a numerical comparison of three different strategies for incorporating linear constraints into QAOA: transforming them into an unconstrained format, introducing penalty dephasing, and utilizing the quantum Zeno effect. We assess the efficiency and effectiveness of these methods using the knapsack problem as a case study. Our findings provide insights into the potential applicability of different encoding methods for various use cases.
Abstract Constrained optimization problems are ubiquitous in science and industry. Quantum algorithms have shown promise in solving optimization problems, yet none of the current algorithms can effectively handle arbitrary constraints. We introduce a technique that uses quantum Zeno dynamics to solve optimization problems with multiple arbitrary constraints, including inequalities. We show that the dynamics of quantum optimization can be efficiently restricted to the in-constraint subspace on a fault-tolerant quantum computer via repeated projective measurements, requiring only a small number of auxiliary qubits and no post-selection. Our technique has broad applicability, which we demonstrate by incorporating it into the quantum approximate optimization algorithm (QAOA) and variational quantum circuits for optimization. We evaluate our method numerically on portfolio optimization problems with multiple realistic constraints and observe better solution quality and higher in-constraint probability than state-of-the-art techniques. We implement a proof-of-concept demonstration of our method on the Quantinuum H1-2 quantum processor.
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.
Constrained combinatorial optimization with strict linear constraints underpins applications in drug discovery, power grids, logistics, and finance, yet remains computationally demanding for classical algorithms, especially at large scales. The Quantum Approximate Optimization Algorithm (QAOA) offers a promising quantum framework, but conventional penalty-based formulations distort optimization landscapes and demand deep circuits, undermining scalability on near-term hardware. In this work, we introduce Hamming Weight Operators, a new class of constraint-aware operators that confine quantum evolution strictly within the feasible subspace. Building on this idea, we develop Adaptive Hamming Weight Operator QAOA, which dynamically selects the most effective operators to construct shallow, problem-tailored circuits. We validate our approach on benchmark tasks from both finance and high-energy physics, specifically portfolio optimization and two-jet clustering with energy balance. Across these problems, our method inherently satisfies all constraints by construction, converges faster, and achieves higher Approximation Ratios than penalty-based QAOA, while requiring roughly half as many gates. By embedding constraint-aware operators into an adaptive variational framework, our approach establishes a scalable and hardware-efficient pathway for solving practical constrained optimization problems on near-term quantum devices.
Constrained combinatorial optimization problems, which are ubiquitous in industry, can be solved by quantum algorithms such as quantum annealing (QA) and the quantum approximate optimization algorithm (QAOA). In these quantum algorithms, constraints are typically implemented with quadratic penalty functions. This penalty method can introduce large energy scales and make interaction graphs much more dense. These effects can result in worse performance of quantum optimization, particularly on near-term devices that have sparse hardware graphs and other physical limitations. In this work, we consider linear Ising penalty functions, which are applied with local fields in the Ising model, as an alternative method for implementing constraints that makes more efficient use of physical resources. We study the behavior of the penalty method in the context of quantum optimization for customer data science problems. Our theoretical analysis and numerical simulations of QA and the QAOA indicate that this penalty method can lead to better performance in quantum optimization than the quadratic method. However, the linear Ising penalty method is not suitable for all problems as it cannot always exactly implement the desired constraint. In cases where the linear method is not successful in implementing all constraints, we propose that schemes involving both quadratic and linear Ising penalties can be effective. Published by the American Physical Society 2024
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.