Exponential Quantum Speedup for Simulation-Based Optimization Applications
Jonas Stein, Müller, Lukas, Leonhard Hölscher, Chnitidis, Georgios, Jezer Jojo, Afrah Farea, M. Serdar Çelebi, Bucher, David, Wulf, Jonathan, Fischer, David, Philipp J. Altmann, Claudia Linnhoff–Popien, Sebastian Feld
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.
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.
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 optimization allows for up to exponential quantum speedups for specific, possibly industrially relevant problems. As the key algorithm in this field, we motivate and discuss the Quantum Approximate Optimization Algorithm (QAOA), which can be understood as a slightly generalized version of Quantum Annealing for gate-based quantum computers. We delve into the quantum circuit implementation of the QAOA, including Hamiltonian simulation techniques for higher-order Ising models, and discuss parameter training using the parameter shift rule. An example implementation with Pennylane source code demonstrates practical application for the Maximum Cut problem. Further, we show how constraints can be incorporated into the QAOA using Grover mixers, allowing to restrict the search space to strictly valid solutions for specific problems. Finally, we outline the Variational Quantum Eigensolver (VQE) as a generalization of the QAOA, highlighting its potential in the NISQ era and addressing challenges such as barren plateaus and ansatz design.
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.
Quantum computing has emerged as a transformative paradigm capable of solving complex computational problems that are intractable for classical computers. Central to the advancement of this technology is the development of efficient quantum algorithms and high fidelity simulations that enable the design, testing, and optimization of quantum solutions before deployment on physical hardware. This study focuses on the design and implementation of quantum algorithms tailored for solving a variety of quantum problems, including quantum chemistry, optimization, and cryptography. Using state of the art simulation platforms such as Qiskit, Cirq, and Pennylane, algorithm performance was evaluated in terms of accuracy, execution time, scalability, and resilience to noise. Benchmarks demonstrate that algorithms such as the Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization Algorithm (QAOA) achieve significant speedups in problem specific domains, while hybrid quantum–classical methods provide robust pathways for near term quantum advantage. Simulation results reveal that algorithmic efficiency can be significantly improved through optimized circuit depth, qubit connectivity mapping, and advanced error mitigation techniques. The findings highlight the potential of simulation driven quantum algorithm development in accelerating the practical realization of quantum computing applications across disciplines such as materials discovery, molecular modeling, secure communications, and complex optimization tasks.
Along with the development of quantum technology, finding useful applications of quantum computers has been a central pursuit. Despite various quantum algorithms have been developed, many of them often require strong input assumptions, which is hardware demanding. In particular, recent advances on dequantization have revealed that the quantum advantage is more of a mere artifact of strong input assumptions. In this work, we propose a variant of these algorithms, leveraging both classical and quantum resources. Provided the classical knowledge (the entries) of the matrix/vector of interest, a classical procedure is used to pre-process this information. Then they are fed into a quantum circuit which is shown to be a block encoding of the matrix of interest. From this block-encoding, we show how to use it to tackle a wide range of problems, including principal component analysis, linear equation solving, Hamiltonian simulation, preparing ground state, and data fitting. We also analyze our protocol, showing that both the classical and quantum procedure can achieve logarithmic complexity in the input dimension, thus implying its potential for near term realization. We then discuss several implications and corollaries of our result. First,, our results suggest there are certain matrices/Hamiltonians where our method can provide exponential improvement compared to the existing ones with respect to the sparsity. Regarding dense linear systems, our method achieves exponential speed-up with respect to the inverse of error tolerance, compared to the best previously known quantum algorithm for dense systems. Last, and most importantly, regarding quantum data fitting, we show how the output of our quantum algorithms can be leveraged to predict unseen data. Thus, it provides an end-to-end application, which has been an open aspect of the previous quantum data fitting algorithm.
Quantum computers have the potential to efficiently solve a system of nonlinear ordinary differential equations (ODEs), which play a crucial role in various industries and scientific fields. However, it remains unclear which system of nonlinear ODEs, and under what assumptions, can achieve exponential speedup using quantum computers. In this work, we introduce a class of systems of nonlinear ODEs that can be efficiently solved on quantum computers, where the efficiency is defined as solving the system with computational complexity of O(Tlog(N)polylog(1/ε)), where T is the evolution time, ε is the allowed error, and N is the number of variables in the system. Specifically, we employ the Koopman-von Neumann linearization to map the system of nonlinear ODEs to Hamiltonian dynamics and find conditions where the norm of the mapped Hamiltonian is preserved and the Hamiltonian is sparse. This allows us to use the optimal Hamiltonian simulation technique for solving the nonlinear ODEs with O(log(N)) overhead. Furthermore, we show that the nonlinear ODEs include a wide range of systems of nonlinear ODEs, such as the nonlinear harmonic oscillators and the short-range Kuramoto model. This is the first concrete example of solving systems of nonlinear ODEs with exponential quantum speedup by the Koopman-von Neumann linearization, although it is noted that this assumes efficient preparation of the initial state and computation of the output. These findings contribute significantly to the application of quantum computers in solving nonlinear problems.