Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms
- URL: http://arxiv.org/abs/2004.06421v2
- Date: Mon, 30 May 2022 04:16:11 GMT
- Title: Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms
- Authors: Kaining Zhang and Min-Hsiu Hsieh and Liu Liu and Dacheng Tao
- Abstract summary: 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.
- Score: 87.04438831673063
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Many quantum algorithms that claim speed-up over their classical counterparts
only generate quantum states as solutions instead of their final classical
description. The additional step to decode quantum states into classical
vectors normally will destroy the quantum advantage in most scenarios because
all existing tomographic methods require runtime that is polynomial with
respect to the state dimension. In this work, we present an efficient read-out
protocol that yields the classical vector form of the generated state, so it
will achieve the end-to-end advantage for those quantum algorithms. Our
protocol suits the case that the output state lies in the row space of the
input matrix, of rank $r$, that is stored in the quantum random access memory.
The quantum resources for decoding the state in $\ell^2$ norm with $\epsilon$
error require $\poly(r,1/\epsilon)$ copies of the output state and $\poly(r,
\kappa^r,1/\epsilon)$ queries to the input oracles, where $\kappa$ is the
condition number of the input matrix. With our read-out protocol, we completely
characterise the end-to-end resources for quantum linear equation solvers and
quantum singular value decomposition. One of our technical tools is an
efficient quantum algorithm for performing the Gram-Schmidt orthonormal
procedure, which we believe, will be of independent interest.
Related papers
- Quantum sampling algorithms for quantum state preparation and matrix block-encoding [0.0]
We first present an algorithm based on QRS that prepares a quantum state $|psi_frangle propto sumN_x=1 f(x)|xrangle$.
We then adapt QRS techniques to the matrix block-encoding problem and introduce a QRS-based algorithm for block-encoding a given matrix $A = sum_ij A_ij |irangle langle j|$.
arXiv Detail & Related papers (2024-05-19T03:46:11Z) - Spin coupling is all you need: Encoding strong electron correlation on quantum computers [0.0]
We show that quantum computers can efficiently simulate strongly correlated molecular systems by directly encoding the dominant entanglement structure in the form of spin-coupled initial states.
Our work paves the way towards scalable quantum simulation of electronic structure for classically challenging systems.
arXiv Detail & Related papers (2024-04-29T17:14:21Z) - Quantum process tomography of continuous-variable gates using coherent
states [49.299443295581064]
We demonstrate the use of coherent-state quantum process tomography (csQPT) for a bosonic-mode superconducting circuit.
We show results for this method by characterizing a logical quantum gate constructed using displacement and SNAP operations on an encoded qubit.
arXiv Detail & Related papers (2023-03-02T18:08:08Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Efficient Bipartite Entanglement Detection Scheme with a Quantum
Adversarial Solver [89.80359585967642]
Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits.
We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
arXiv Detail & Related papers (2022-03-15T09:46:45Z) - Quantum algorithms for estimating quantum entropies [6.211541620389987]
We propose quantum algorithms to estimate the von Neumann and quantum $alpha$-R'enyi entropies of an fundamental quantum state.
We also show how to efficiently construct the quantum entropy circuits for quantum entropy estimation using single copies of the input state.
arXiv Detail & Related papers (2022-03-04T15:44:24Z) - Quantum State Preparation with Optimal Circuit Depth: Implementations
and Applications [10.436969366019015]
We show that any $Theta(n)$-depth circuit can be prepared with a $Theta(log(nd)) with $O(ndlog d)$ ancillary qubits.
We discuss applications of the results in different quantum computing tasks, such as Hamiltonian simulation, solving linear systems of equations, and realizing quantum random access memories.
arXiv Detail & Related papers (2022-01-27T13:16:30Z) - Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
"Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation.
We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
arXiv Detail & Related papers (2021-12-09T19:00:00Z) - Efficient Verification of Anticoncentrated Quantum States [0.38073142980733]
I present a novel method for estimating the fidelity $F(mu,tau)$ between a preparable quantum state $mu$ and a classically specified target state $tau$.
I also present a more sophisticated version of the method, which uses any efficiently preparable and well-characterized quantum state as an importance sampler.
arXiv Detail & Related papers (2020-12-15T18:01:11Z)
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.