Exponential Quantum Speedup for Simulation-Based Optimization Applications
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914949632098304 |
|---|---|
| author | Stein, Jonas Müller, Lukas Hölscher, Leonhard Chnitidis, Georgios Jojo, Jezer Farea, Afrah Çelebi, Mustafa Serdar Bucher, David Wulf, Jonathan Fischer, David Altmann, Philipp Linnhoff-Popien, Claudia Feld, Sebastian |
| author_facet | Stein, Jonas Müller, Lukas Hölscher, Leonhard Chnitidis, Georgios Jojo, Jezer Farea, Afrah Çelebi, Mustafa Serdar Bucher, David Wulf, Jonathan Fischer, David Altmann, Philipp Linnhoff-Popien, Claudia Feld, Sebastian |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_08482 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Exponential Quantum Speedup for Simulation-Based Optimization Applications Stein, Jonas Müller, Lukas Hölscher, Leonhard Chnitidis, Georgios Jojo, Jezer Farea, Afrah Çelebi, Mustafa Serdar Bucher, David Wulf, Jonathan Fischer, David Altmann, Philipp Linnhoff-Popien, Claudia Feld, Sebastian Quantum Physics Emerging Technologies 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. |
| title | Exponential Quantum Speedup for Simulation-Based Optimization Applications |
| topic | Quantum Physics Emerging Technologies |
| url | https://arxiv.org/abs/2305.08482 |