Exponential Quantum Speedup for Simulation-Based Optimization Applications

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.