Quantum Simulation-based Optimization (QuSO) is a recently proposed class of optimization problems that entails industrially relevant problems characterized by cost functions or constraints that depend on summary statistic information about the simulation of a physical system or process. This work extends initial theoretical results that proved an up-to-exponential speedup for the simulation component of the QAOA-based QuSO solver for the unit commitment problem to an end-to-end speedup, explicitly including the outer optimization component. The numerical experiments were conducted using randomly generated power grid instances of varying sizes and loads that adhere to the physical properties of real world power grids. Exploiting clever classical pre-computation, we develop a very efficient classical quantum circuit simulation that bypasses costly ancillary qubit requirements of the original algorithm, allowing for large-scale experiments. We show that 16 QAOA layers suffice to outperform a strong classical baseline for problems involving up to 14 qubits in scenarios of high load and perform on par otherwise. In summary, our results thus extend previous partial quantum speedup results for QuSO problems to an end-to-end setting that encompasses the runtime of the complete algorithm for a problem of industrial relevance.
Quantum Simulation-based Optimization (QuSO) is a recently proposed class of optimization problems that entails industrially relevant problems characterized by cost functions or constraints that depend on summary statistic information about the simulation of a physical system or process. This work extends initial theoretical results that proved an up-to-exponential speedup for the simulation component of the QAOA-based QuSO solver for the unit commitment problem to an end-to-end speedup, explicitly including the outer optimization component. The numerical experiments were conducted using randomly generated power grid instances of varying sizes and loads that adhere to the physical properties of real world power grids. Exploiting clever classical pre-computation, we develop a very efficient classical quantum circuit simulation that bypasses costly ancillary qubit requirements of the original algorithm, allowing for large-scale experiments. We show that 16 QAOA layers suffice to outperform a strong classical baseline for problems involving up to 14 qubits in scenarios of high load and perform on par otherwise. In summary, our results thus extend previous partial quantum speedup results for QuSO problems to an end-to-end setting that encompasses the runtime of the complete algorithm for a problem of industrial relevance.
The simulation of many industrially relevant physical processes can be executed up to exponentially faster using quantum algorithms. However, this speedup can only be leveraged if the data input and output of the simulation can be implemented efficiently. While we show that recent advancements for optimal state preparation can effectively solve the problem of data input at a moderate cost of ancillary qubits in many cases, the output problem can provably not be solved efficiently in general. By acknowledging that many simulation problems arise only as a subproblem of a larger optimization problem in many practical applications however, we identify and define a class of practically relevant problems that does not suffer from the output problem: Quantum Simulation-based Optimization (QuSO). QuSO represents optimization problems whose objective function and/or constraints depend on summary statistic information on the result of a simulation, i.e., information that can be efficiently extracted from a quantum state vector. In this article, we focus on the LinQuSO subclass of QuSO, which is characterized by the linearity of the simulation problem, i.e., the simulation problem can be formulated as a system of linear equations. By cleverly combining the quantum singular value transformation (QSVT) with the quantum approximate optimization algorithm (QAOA), we prove that a large subgroup of LinQuSO problems can be solved with up to exponential quantum speedups with regards to their simulation component. Finally, we present two practically relevant use cases that fall within this subgroup of QuSO problems.
Abstract Engineering design processes involve iterative design evaluations requiring numerous computationally intensive numerical simulations. Quantum algorithms promise substantial speedups for specific tasks relevant to engineering simulations. However, these advantages quickly vanish when considering data input and output on quantum computers. The recently introduced quantum simulation-based optimization (QuSO) framework circumvents this limitation by treating simulations as subproblems within a larger optimization problem. Here we adapt and implement QuSO for a simplified cooling system design problem, validate correctness in statevector simulations, and present a detailed gate-level complexity analysis for a single QuSO iteration. We express the scaling in terms of problem parameters and quantum approximate optimization algorithm (QAOA) depth and iterations. We show that the cost function can be coherently computed over a superposition of exponentially many configurations using circuits of polynomial complexity. This does not yield a speedup for a single simulation instance, but it enables potential advantages arising from the subsequent QAOA-based search over configurations. The study serves as a proof-of-concept for integrating fault-tolerant quantum subroutines with simulation-based optimization in engineering workflows, clarifying both promise and practical limitations.
In the present Noisy Intermediate-Scale Quantum (NISQ), hybrid algorithms that leverage classical resources to reduce quantum costs are particularly appealing. We formulate and apply such a hybrid quantum-classical algorithm to a power system optimization problem called Unit Commitment, which aims to satisfy a target power load at minimal cost. Our algorithm extends the Quantum Approximation Optimization Algorithm (QAOA) with a classical minimizer in order to support mixed binary optimization. Using Qiskit, we simulate results for sample systems to validate the effectiveness of our approach. We also compare to purely classical methods. Our results indicate that classical solvers are effective for our simulated Unit Commitment instances with fewer than 400 power generation units. However, for larger problem instances, the classical solvers either scale exponentially in runtime or must resort to coarse approximations. This opens the door to potential quantum advantage for systems with several hundred units, though quantum error correction may be necessary at this scale.
The rapid development of quantum computing has provided a ground-breaking tool for solving problems that are insurmountable on classical computers. In the power system domain, quantum computing is still in the nascent stage, with limited but ongoing studies. The Quantum Approximation Optimization Algorithm (QAOA) has been applied in solving several NPhard problems and can be further studied to address challenging problems in power systems. Key applications include contingency analysis, optimal power flow, and unit commitment, among others. With the significant integration of renewable energy, the intermittent nature of renewable energy introduces substantial volatility to the system. An overhead contingency analysis is required to evaluate the possible system outage scenarios, which will identify critical contingencies to maintain system stability. However, the contingency analysis is a prototypical NP-Hard problem, requiring substantial classical computation resources. In this work, QAOA is developed for theN−kcontingency analysis on line contingency as well as the general contingency scenarios, with the aim of minimizing the shedding of the power load while ensuring the power flow constraints. A tailored objective function is developed to encode theN−kcontingency condition as well as the power flow loss constraints into a problem Hamiltonian for QAOA computation. The developed method is verified on IEEE 9- and 14-bus systems compared with classical methods as the baseline. In addition, a QAOA parameter study including the number of QAOA parameters, the number of repetitions of the quantum circuits execution, and the number of iteration steps of the classical optimization algorithm, is conducted to offer insights for the parameter tuning under different problem sizes. This work is anticipated to establish a quantum framework for solving critical and complex power system problems in the Noisy intermediate-scale quantum (NISQ) era.
Alternating Current Optimal Power Flow Unit Commitment (AC-OPF-UC) is a difficult mixed-integer nonlinear optimization problem that combines binary generator commitment decisions with nonconvex continuous AC power-flow constraints. In this work, we investigate whether hybrid quantum-classical variational algorithms can improve the solution of single-period AC-OPF-UC relative to classical approaches. To the best of our knowledge, this is the first study to directly evaluate quantum or hybrid quantum-classical algorithms for the full AC-OPF-UC problem. We consider two candidate algorithms for improving AC-OPF-UC solution quality relative to purely classical methods on ideal quantum hardware. The first applies QAOA directly to a fully discretized formulation of the problem, with equality and inequality constraints incorporated through penalty terms and slack variables. Although conceptually straightforward, this approach requires a prohibitively large number of qubits even for small instances. The second, qubit-efficient approach encodes only the binary generator status variables on a quantum computer, while optimizing the continuous power-flow variables classically for each sampled bitstring. We benchmark this method on randomly generated AC-OPF-UC instances with 5 to 13 generators and compare it against SCIP, SMAC, and uniform random sampling. Our simulations show that the qubit-efficient hybrid method does not outperform uniform sampling. These results suggest that in order to establish potential advantage of the variational hybrid strategy considered here over the best classical algorithms, if any, much larger system sizes (25+ generators) need to be tested, which is beyond our computational capacity. Alternatively, different approaches, such as quantum versions of branch-and-bound methods, may be more promising.
In this project summary paper, we summarize the key results and use-cases explored in the German Federal Ministry of Education and Research (BMBF) funded project "Q-GRID" which aims to assess potential quantum utility optimization applications in the electrical grid. The project focuses on two layers of optimization problems relevant to decentralized energy generation and transmission as well as novel energy transportation/exchange methods such as Peer-2-Peer energy trading and microgrid formation. For select energy grid optimization problems, we demonstrate exponential classical optimizer runtime scaling even for small problem instances, and present initial findings that variational quantum algorithms such as QAOA and hybrid quantum annealing solvers may provide more favourable runtime scaling to obtain similar solution quality. These initial results suggest that quantum computing may be a key enabling technology in the future energy transition insofar that they may be able to solve business problems which are already challenging at small problem instance sizes.