Accelerating Quantum Algorithms with Precomputation
arXiv:2305.09638 · doi:10.22331/q-2024-02-22-1264
Abstract
Real-world applications of computing can be extremely time-sensitive. It would be valuable if we could accelerate such tasks by performing some of the work ahead of time. Motivated by this, we propose a cost model for quantum algorithms that allows quantum precomputation, i.e., for a polynomial amount of "free" computation before the input to an algorithm is fully specified, and methods for taking advantage of it. We analyze two families of unitaries that are asymptotically more efficient to implement in this cost model than in the standard one. The first example of quantum precomputation, based on density matrix exponentiation, could offer an exponential advantage under certain conditions. The second example uses a variant of gate teleportation to achieve a quadratic advantage when compared with implementing the unitaries directly. These examples hint that quantum precomputation may offer a new arena in which to seek quantum advantage.
References in corpus (30)
- Quantum Machine Learning
- Quantum algorithm for solving linear systems of equations
- Quantum Teleportation is a Universal Computational Primitive
- A Quantum Approximate Optimization Algorithm
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Quantum principal component analysis
- Quantum Error Correction for Quantum Memories
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
- Optical quantum computation using cluster states
- Quantum advantage in learning from experiments
- A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery
- Methodology for quantum logic gate constructions
- Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization
- Magic State Distillation: Not as Costly as You Think
- Instantaneous Quantum Computation
- Simulating chemistry efficiently on fault-tolerant quantum computers
- Focus beyond quadratic speedups for error-corrected quantum advantage
- Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
- Hadamard-free circuits expose the structure of the Clifford group
- Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization
- Hamiltonian Simulation with Optimal Sample Complexity
- Diagonal gates in the Clifford hierarchy
- Generalized swap networks for near-term quantum computing
- An efficient magic state approach to small angle rotations
- Linear and logarithmic time compositions of quantum many-body operators
- Improved Quantum Algorithms for Fidelity Estimation
- Complexity of quantum state verification in the quantum linear systems problem
- Flexible layout of surface code computations using AutoCCZ states
- Revisiting dequantization and quantum advantage in learning tasks