Efficient Pauli channel estimation with logarithmic quantum memory
- URL: http://arxiv.org/abs/2309.14326v2
- Date: Thu, 30 Nov 2023 19:11:59 GMT
- Title: Efficient Pauli channel estimation with logarithmic quantum memory
- Authors: Sitan Chen and Weiyuan Gong
- Abstract summary: We show that a protocol can estimate the eigenvalues of a Pauli channel to error $epsilon$ using only $O(log n/epsilon2)$ ancilla qubits and $tildeO(n2/epsilon2)$ measurements.
Our results imply, to our knowledge, the first quantum learning task where logarithmically many qubits of quantum memory suffice for an exponential statistical advantage.
- Score: 10.95781315121668
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Here we revisit one of the prototypical tasks for characterizing the
structure of noise in quantum devices: estimating every eigenvalue of an
$n$-qubit Pauli noise channel to error $\epsilon$. Prior work (Chen et al.,
2022) proved no-go theorems for this task in the practical regime where one has
a limited amount of quantum memory, e.g. any protocol with $\le 0.99n$ ancilla
qubits of quantum memory must make exponentially many measurements, provided it
is non-concatenating. Such protocols can only interact with the channel by
repeatedly preparing a state, passing it through the channel, and measuring
immediately afterward.
This left open a natural question: does the lower bound hold even for general
protocols, i.e. ones which chain together many queries to the channel,
interleaved with arbitrary data-processing channels, before measuring?
Surprisingly, in this work we show the opposite: there is a protocol that can
estimate the eigenvalues of a Pauli channel to error $\epsilon$ using only
$O(\log n/\epsilon^2)$ ancilla qubits and $\tilde{O}(n^2/\epsilon^2)$
measurements. In contrast, we show that any protocol with zero ancilla, even a
concatenating one, must make $\Omega(2^n/\epsilon^2)$ measurements, which is
tight.
Our results imply, to our knowledge, the first quantum learning task where
logarithmically many qubits of quantum memory suffice for an exponential
statistical advantage.
Related papers
- On the sample complexity of purity and inner product estimation [8.94496959777308]
We study the sample complexity of the tasks quantum purity estimation and quantum inner product estimation.
In purity estimation, we are to estimate $tr(rho2)$ of an unknown quantum state $rho$ to additive error $epsilon$.
For quantum inner product estimation, Alice and Bob are to estimate $tr(rhosigma)$ to additive error $epsilon$ given copies of unknown quantum state $rho$ and $sigma$.
arXiv Detail & Related papers (2024-10-16T16:17:21Z) - Circuit Complexity of Sparse Quantum State Preparation [0.0]
We show that any $n$-qubit $d$-sparse quantum state can be prepared by a quantum circuit of size $O(fracdnlog d)$ and depth $Theta(log dn)$ using at most $O(fracndlog d )$ ancillary qubits.
We also establish the lower bound $Omega(fracdnlog(n + m) + log d + n)$ on the circuit size with $m$ ancillary qubits available.
arXiv Detail & Related papers (2024-06-23T15:28:20Z) - Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$.
We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
arXiv Detail & Related papers (2024-01-17T18:59:38Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods.
We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
arXiv Detail & Related papers (2023-03-03T18:23:20Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation.
We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z) - Quantum advantages for Pauli channel estimation [2.5496329090462626]
entangled measurements provide an exponential advantage in sample complexity for Pauli channel estimation.
We show how to apply the ancilla-assisted estimation protocol to a practical quantum benchmarking task.
arXiv Detail & Related papers (2021-08-19T04:10:28Z) - Fault-tolerant Coding for Quantum Communication [71.206200318454]
encode and decode circuits to reliably send messages over many uses of a noisy channel.
For every quantum channel $T$ and every $eps>0$ there exists a threshold $p(epsilon,T)$ for the gate error probability below which rates larger than $C-epsilon$ are fault-tolerantly achievable.
Our results are relevant in communication over large distances, and also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise.
arXiv Detail & Related papers (2020-09-15T15:10:50Z) - Succinct Blind Quantum Computation Using a Random Oracle [0.8702432681310399]
We give a new universal blind quantum computation protocol.
The protocol's first phase is succinct, that is, its complexity is independent of circuit size.
arXiv Detail & Related papers (2020-04-27T07:47:11Z) - Secure multi-party quantum computation with few qubits [0.0]
We consider the task of secure multi-party distributed quantum computation on a quantum network.
We propose a protocol based on quantum error correction which reduces the number of necessary qubits.
We showcase our protocol on a small example for a 7-node network.
arXiv Detail & Related papers (2020-04-22T10:48:30Z) - 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) - Communication Cost of Quantum Processes [49.281159740373326]
A common scenario in distributed computing involves a client who asks a server to perform a computation on a remote computer.
An important problem is to determine the minimum amount of communication needed to specify the desired computation.
We analyze the total amount of (classical and quantum) communication needed by a server in order to accurately execute a quantum process chosen by a client.
arXiv Detail & Related papers (2020-02-17T08:51:42Z)
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.