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.
18 October 2024 in IEEE Transactions on Smart Grid
Power grid partitioning is an important requirement for resilient distribution grids. Since electricity production is progressively shifted to the distribution side, dynamic identification of self-reliant grid subsets becomes crucial for operation. This problem can be represented as a modification to the well-known NP-hard Community Detection (CD) problem. We formulate it as a Quadratic Unconstrained Binary Optimization (QUBO) problem suitable for solving using quantum computation, which is expected to find better-quality partitions faster. The formulation aims to find communities with maximal self-sufficiency and minimal power flowing between them. To assess quantum optimization for sizeable problems, we develop a hierarchical divisive method that solves sub-problem QUBOs to perform grid bisections. Furthermore, we propose a customization of the Louvain heuristic that includes self-reliance. In the evaluation, we first demonstrate that this problem examines exponential runtime scaling classically. Then, using different IEEE power system test cases, we benchmark the solution quality for multiple approaches: D-Wave’s hybrid quantum-classical solvers, classical heuristics, and a branch-and-bound solver. As a result, we observe that the hybrid solvers provide very promising results, both with and without the divisive algorithm, regarding solution quality achieved within a given time frame. Directly utilizing D-Wave’s Quantum Annealing (QA) hardware shows inferior partitioning.
30 May 2024 in IEEE Transactions on Quantum Engineering
Demand Side Response (DSR) is a strategy that enables consumers to actively participate in managing electricity demand. It aims to alleviate strain on the grid during high demand and promote a more balanced and efficient use of (renewable) electricity resources. We implement DSR through discount scheduling, which involves offering discrete price incentives to consumers to adjust their electricity consumption patterns to times when their local energy mix consists of more renewable energy. Since we tailor the discounts to individual customers' consumption, the Discount Scheduling Problem (DSP) becomes a large combinatorial optimization task. Consequently, we adopt a hybrid quantum computing approach, using D-Wave's Leap Hybrid Cloud. We benchmark Leap against Gurobi, a classical Mixed Integer optimizer in terms of solution quality at fixed runtime and fairness in terms of discount allocation. Furthermore, we propose a large-scale decomposition algorithm/heuristic for the DSP, applied with either quantum or classical computers running the subroutines, which significantly reduces the problem size while maintaining solution quality. Using synthetic data generated from real-world data, we observe that the classical decomposition method obtains the best overall solution quality for problem sizes up to 3200 consumers, however, the hybrid quantum approach provides more evenly distributed discounts across consumers.
The analysis of network structure is essential to many scientific areas ranging from biology to sociology. As the computational task of clustering these networks into partitions, i.e., solving the community detection problem, is generally NP-hard, heuristic solutions are indispensable. The exploration of expedient heuristics has led to the development of particularly promising approaches in the emerging technology of quantum computing. Motivated by the substantial hardware demands for all established quantum community detection approaches, we introduce a novel QUBO-based approach that only needs number-of-nodes qubits and is represented by a QUBO matrix as sparse as the input graph’s adjacency matrix. The substantial improvement in the sparsity of the QUBO matrix, which is typically very dense in related work, is achieved through the novel concept of separation nodes. Instead of assigning every node to a community directly, this approach relies on the identification of a separation-node set, which, upon its removal from the graph, yields a set of connected components, representing the core components of the communities. Employing a greedy heuristic to assign the nodes from the separation-node sets to the identified community cores, subsequent experimental results yield a proof of concept by achieving an up to 95% optimal solution quality on three established real-world benchmark datasets. This work hence displays a promising approach to NISQ-ready quantum community detection, catalyzing the application of quantum computers for the network structure analysis of large-scale, real-world problem instances.
The quantum approximate optimization algorithm (QAOA) is a leading hybrid heuristic for combinatorial optimization, but efficiently handling hard constraints remains a significant challenge. -mixers successfully confine quantum state evolution to a feasible subspace, such as the Hamming-weight-1 sector for one-hot constraints. On the contrary, warm-starting biases the search toward promising regions based on preliminary solutions. Combining these two techniques requires maintaining the essential alignment between the initial state and the mixer Hamiltonian to preserve convergence guarantees. Previous work demonstrated warm-starting with -mixers via a biased initial state, but relying only on standard mixer Hamiltonians. Consequently, the initial state is no longer a ground state of the mixer. In this work, we overcome these limitations by formulating a warm-started -mixer Hamiltonian for one-hot constraints and proving its ground-state properties. Furthermore, we provide a shallow circuit implementation suitable for NISQ implementations. We embed the warm-starting into a classical heuristic that iteratively updates the bias based on previous samples, called iterative warm-starting (IWS). Extensive numerical simulations on Max- -Cut and traveling salesperson problem instances demonstrate that IWS-QAOA significantly accelerates the solution-finding process, increasing the probability of sampling optimal solutions by orders of magnitude compared to standard XY-QAOA. Finally, we validate our approach on the ibm_boston QPU using hardware-tailored 144-qubit problem instances. By coupling IWS-QAOA with a greedy steepest-descent post-processing strategy to repair infeasible measurements caused by hardware noise, we successfully identify optimal solutions on actual quantum devices.
The analysis of network structure is essential to many scientific areas, ranging from biology to sociology. As the computational task of clustering these networks into partitions, i.e., solving the community detection problem, is generally NP-hard, heuristic solutions are indispensable. The exploration of expedient heuristics has led to the development of particularly promising approaches in the emerging technology of quantum computing. Motivated by the substantial hardware demands for all established quantum community detection approaches, we introduce a novel QUBO based approach that only needs number-of-nodes many qubits and is represented by a QUBO-matrix as sparse as the input graph's adjacency matrix. The substantial improvement on the sparsity of the QUBO-matrix, which is typically very dense in related work, is achieved through the novel concept of separation-nodes. Instead of assigning every node to a community directly, this approach relies on the identification of a separation-node set, which - upon its removal from the graph - yields a set of connected components, representing the core components of the communities. Employing a greedy heuristic to assign the nodes from the separation-node sets to the identified community cores, subsequent experimental results yield a proof of concept. This work hence displays a promising approach to NISQ-ready quantum community detection, catalyzing the application of quantum computers for the network structure analysis of large scale, real world problem instances.}