Hamiltonian Simulation with Optimal Sample Complexity
arXiv:1608.00281 · doi:10.1038/s41534-017-0013-7
Abstract
We investigate the sample complexity of Hamiltonian simulation: how many copies of an unknown quantum state are required to simulate a Hamiltonian encoded by the density matrix of that state? We show that the procedure proposed by Lloyd, Mohseni, and Rebentrost [Nat. Phys., 10(9):631--633, 2014] is optimal for this task. We further extend their method to the case of multiple input states, showing how to simulate any Hermitian polynomial of the states provided. As applications, we derive optimal algorithms for commutator simulation and orthogonality testing, and we give a protocol for creating a coherent superposition of pure states, when given sample access to those states. We also show that this sample-based Hamiltonian simulation can be used as the basis of a universal model of quantum computation that requires only partial swap operations and simple single-qubit states.
Accepted talk at TQC 2016, 3 Fig, 5 Appendices
References in corpus (10)
- Quantum algorithm for solving linear systems of equations
- Exponential algorithmic speedup by quantum walk
- Optimal Hamiltonian Simulation by Quantum Signal Processing
- Fixed-point quantum search with an optimal number of queries
- Measurement Protocol for the Entanglement Spectrum of Cold Atoms
- Semiconductor few-electron quantum dot operated as a bipolar spin filter
- Experimental Spin Ratchet
- Building all Time Evolutions with Rotationally Invariant Hamiltonians
- Universal Quantum Emulator
- Experimentally superposing two pure states with partial prior knowledge
Cited by in corpus (50)
- Quantum Machine Learning
- Quantum Chemistry in the Age of Quantum Computing
- Hamiltonian Simulation by Qubitization
- Quantum Hopfield neural network
- Restrictions on realizable unitary operations imposed by symmetry and locality
- Quantum algorithm for Petz recovery channels and pretty good measurements
- Bayesian Deep Learning on a Quantum Computer
- Quantum linear systems algorithms: a primer
- Quantum Computing: An Overview Across the System Stack
- Hamiltonian Simulation by Uniform Spectral Amplification
- Quantum Algorithm for Fidelity Estimation
- New Quantum Algorithms for Computing Quantum Entropies and Distances
- Generative training of quantum Boltzmann machines with hidden units
- Multivariate trace estimation in constant quantum depth
- Fast Quantum Algorithms for Trace Distance Estimation
- Wave Matrix Lindbladization I: Quantum Programs for Simulating Markovian Dynamics
- Quantum Speed-ups for Semidefinite Programming
- Protocol for implementing quantum nonparametric learning with trapped ions
- Realizing quantum linear regression with auxiliary qumodes
- Statistical Complexity of Quantum Learning
- Quantum simulation of colour in perturbative quantum chromodynamics
- Quantum Next Generation Reservoir Computing: An Efficient Quantum Algorithm for Forecasting Quantum Dynamics
- Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
- Quantum approximate algorithm for NP optimization problems with constraints
- Quantum Semi-Supervised Kernel Learning
- Statistical Limits of Supervised Quantum Learning
- Accelerating Quantum Algorithms with Precomputation
- An invitation to the sample complexity of quantum hypothesis testing
- Double-bracket quantum algorithms for quantum imaginary-time evolution
- Quantum algorithms for matrix geometric means
- Quantum Dynamic Programming
- QSlack: A slack-variable approach for variational quantum semi-definite programming
- A Quantum Algorithm for Dynamic Mode Decomposition Integrated with a Quantum Differential Equation Solver
- Approximating Hamiltonian dynamics with the Nyström method
- The Quantum Supremacy Tsirelson Inequality
- Time-Efficient Quantum Entropy Estimator via Samplizer
- Double-bracket algorithm for quantum signal processing without post-selection
- Sample-based Hamiltonian and Lindbladian simulation: Non-asymptotic analysis of sample complexity
- Batched quantum state exponentiation and quantum Hebbian learning
- Quantum Lower Bounds by Sample-to-Query Lifting
- Parallel Quantum Signal Processing Via Polynomial Factorization
- Digital Quantum Simulations of the Non-Resonant Open Tavis-Cummings Model
- Quantum approximated cloning-assisted density matrix exponentiation
- Resource-efficient algorithm for estimating the trace of quantum state powers
- Quantum Machine Learning For Classical Data
- Towards Quantum Universal Hypothesis Testing
- Phase Estimation with Compressed Controlled Time Evolution
- Singular value transformation for unknown quantum channels
- Fast algorithm for quantum polar decomposition, pretty-good measurements, and the Procrustes problem
- Synthesis of Energy-Conserving Quantum Circuits with XY interaction