Quantum Phase Estimation by Compressed Sensing
- URL: http://arxiv.org/abs/2306.07008v4
- Date: Wed, 11 Sep 2024 12:46:11 GMT
- Title: Quantum Phase Estimation by Compressed Sensing
- Authors: Changhao Yi, Cunlu Zhou, Jun Takahashi,
- Abstract summary: We present a new Heisenberg-limited quantum phase estimation algorithm for early quantum computers based on compressed sensing.
Our algorithm is able to recover the frequency with a total runtime $mathcalO(epsilon-1textpolylog(epsilon-1))$, where $epsilon$ is the accuracy.
We also consider the more general quantum eigenvalue estimation problem (QEEP) and show numerically that the off-grid compressed sensing can be a strong candidate for solving the QEEP.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As a signal recovery algorithm, compressed sensing is particularly useful when the data has low-complexity and samples are rare, which matches perfectly with the task of quantum phase estimation (QPE). In this work we present a new Heisenberg-limited QPE algorithm for early quantum computers based on compressed sensing. More specifically, given many copies of a proper initial state and queries to some unitary operators, our algorithm is able to recover the frequency with a total runtime $\mathcal{O}(\epsilon^{-1}\text{poly}\log(\epsilon^{-1}))$, where $\epsilon$ is the accuracy. Moreover, the maximal runtime satisfies $T_{\max}\epsilon \ll \pi$, which is comparable to the state of art algorithms, and our algorithm is also robust against certain amount of noise from sampling. We also consider the more general quantum eigenvalue estimation problem (QEEP) and show numerically that the off-grid compressed sensing can be a strong candidate for solving the QEEP.
Related papers
- On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
lattice-based cryptography is one of the main candidates of post-quantum cryptography.
cryptographic security against quantum attackers is based on lattice problems like the shortest vector problem (SVP)
Asymptotic quantum speedups for solving SVP are known and rely on Grover's search.
arXiv Detail & Related papers (2024-10-17T16:54:41Z) - Classically estimating observables of noiseless quantum circuits [36.688706661620905]
We present a classical algorithm for estimating expectation values of arbitrary observables on most quantum circuits.
For non-classically-simulable input states or observables, the expectation values can be estimated by augmenting our algorithm with classical shadows of the relevant state or observable.
arXiv Detail & Related papers (2024-09-03T08:44:33Z) - Accelerated Quantum Amplitude Estimation without QFT [0.0]
We put forward a Quantum Amplitude Estimation algorithm delivering superior performance (lower quantum computational complexity and faster classical computation parts) compared to the approaches available to-date.
The correctness of the algorithm and the $O(frac1varepsilon)$ bound on quantum computational complexity are supported by precise proofs.
arXiv Detail & Related papers (2024-07-23T18:49:11Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer.
Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.
We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
arXiv Detail & Related papers (2024-05-14T15:28:37Z) - Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions [13.16814860487575]
We present quantum algorithms for sampling from nonlogconcave probability distributions.
$f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
arXiv Detail & Related papers (2023-10-17T17:55:32Z) - Measuring the Loschmidt amplitude for finite-energy properties of the
Fermi-Hubbard model on an ion-trap quantum computer [27.84599956781646]
We study the operation of a quantum-classical time-series algorithm on a present-day quantum computer.
Specifically, we measure the Loschmidt amplitude for the Fermi-Hubbard model on a $16$-site ladder geometry (32 orbitals) on the Quantinuum H2-1 trapped-ion device.
We numerically analyze the influence of noise on the full operation of the quantum-classical algorithm by measuring expectation values of local observables at finite energies.
arXiv Detail & Related papers (2023-09-19T11:59:36Z) - Even shorter quantum circuit for phase estimation on early
fault-tolerant quantum computers with applications to ground-state energy
estimation [5.746732081406236]
We develop a phase estimation method with a distinct feature.
The total cost of the algorithm satisfies the Heisenberg-limited scaling $widetildemathcalO(epsilon-1)$.
Our algorithm may significantly reduce the circuit depth for performing phase estimation tasks on early fault-tolerant quantum computers.
arXiv Detail & Related papers (2022-11-22T03:15:40Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
We develop quantum algorithms for sampling logconcave distributions and for estimating their normalizing constants.
We exploit quantum analogs of the Monte Carlo method and quantum walks.
We also prove a $1/epsilon1-o(1)$ quantum lower bound for estimating normalizing constants.
arXiv Detail & Related papers (2022-10-12T19:10:43Z) - Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
We analyze and optimize an improved quantum algorithm for topological data analysis.
We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation.
We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
arXiv Detail & Related papers (2022-09-27T17:56:15Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
We present an efficient read-out protocol that yields the classical vector form of the generated state.
Our protocol suits the case that the output state lies in the row space of the input matrix.
One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
arXiv Detail & Related papers (2020-04-14T11:05:26Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.