Calculating response functions of coupled oscillators using quantum phase estimation

Abstract

We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. The functional form of these response functions can be mapped to a corresponding eigenproblem of a Hermitian matrix $H$, thus suggesting the use of quantum phase estimation. Our proposed quantum algorithm operates in the standard $s$-sparse, oracle-based query access model. For a network of $N$ oscillators with maximum norm $\Vert H{\Vert }_{\max }$, and when the eigenvalue tolerance $\epsilon$ is much smaller than the minimum eigenvalue gap, we use $\mathcal{O}(\log (Ns\Vert H{\Vert }_{\max }/\epsilon )$ algorithmic qubits and obtain a rigorous worst-case query complexity upper bound $\mathcal{O}(s\Vert H{\Vert }_{\max }/({\delta }^2\epsilon ))$ up to logarithmic factors, where $\delta$ denotes the desired precision on the coefficients appearing in the response functions. Crucially, our proposal does not suffer from the infamous state preparation bottleneck and can as such potentially achieve large quantum speedups compared to relevant classical methods. As a proof-of-principle of exponential quantum speedup, we show that a simple adaptation of our algorithm solves the random glued-trees problem in polynomial time. We discuss practical limitations as well as potential improvements for quantifying finite size, end-to-end complexities for application to relevant instances.

12+10 pages, 8 figures

References in corpus (25)

• A variational eigenvalue solver on a quantum processor
• Quantum computational chemistry
• Perfect state transfer in quantum spin networks
• The Variational Quantum Eigensolver: a review of methods and best practices
• Quantum random access memory
• Hamiltonian Simulation by Qubitization
• Quantum algorithms for quantum chemistry and quantum materials science
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• On the relationship between continuous- and discrete-time quantum walk
• Black-box superconducting circuit quantization
• Preconditioned quantum linear system algorithm
• Efficient Bayesian Phase Estimation
• Quantum algorithms and the finite element method
• Quantum phase estimation of multiple eigenvalues for small-scale (noisy) experiments
• Quantum arithmetic with the Quantum Fourier Transform
• Quantum Algorithm for Simulating the Wave Equation
• Improved Techniques for Preparing Eigenstates of Fermionic Hamiltonians
• Black-box quantum state preparation without arithmetic
• Quantum Algorithm for Spectral Measurement with Lower Gate Count
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Complete monotonicity of some functions involving polygamma functions
• Exponential quantum speedup in simulating coupled classical oscillators
• Simultaneous estimation of multiple eigenvalues with short-depth quantum circuit on early fault-tolerant quantum computers
• Heisenberg-limited quantum phase estimation of multiple eigenvalues with few control qubits
• Lecture Notes on Quantum Electrical Circuits

Cited by in corpus (2)

• End-to-End Quantum Algorithm for Topology Optimization in Structural Mechanics
• Quantum oracles for the finite element method