Exponential separations between learning with and without quantum memory
- URL: http://arxiv.org/abs/2111.05881v1
- Date: Wed, 10 Nov 2021 19:03:49 GMT
- Title: Exponential separations between learning with and without quantum memory
- Authors: Sitan Chen, Jordan Cotler, Hsin-Yuan Huang, Jerry Li
- Abstract summary: We study the power of quantum memory for learning properties of quantum systems and dynamics.
Many state-of-the-art learning algorithms require access to an additional external quantum memory.
We show that this trade-off is inherent in a wide range of learning problems.
- Score: 17.763817187554096
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the power of quantum memory for learning properties of quantum
systems and dynamics, which is of great importance in physics and chemistry.
Many state-of-the-art learning algorithms require access to an additional
external quantum memory. While such a quantum memory is not required a priori,
in many cases, algorithms that do not utilize quantum memory require much more
data than those which do. We show that this trade-off is inherent in a wide
range of learning problems. Our results include the following:
(1) We show that to perform shadow tomography on an $n$-qubit state rho with
$M$ observables, any algorithm without quantum memory requires $\Omega(\min(M,
2^n))$ samples of rho in the worst case. Up to logarithmic factors, this
matches the upper bound of [HKP20] and completely resolves an open question in
[Aar18, AR19].
(2) We establish exponential separations between algorithms with and without
quantum memory for purity testing, distinguishing scrambling and depolarizing
evolutions, as well as uncovering symmetry in physical dynamics. Our
separations improve and generalize prior work of [ACQ21] by allowing for a
broader class of algorithms without quantum memory.
(3) We give the first tradeoff between quantum memory and sample complexity.
We prove that to estimate absolute values of all $n$-qubit Pauli observables,
algorithms with $k < n$ qubits of quantum memory require at least
$\Omega(2^{(n-k)/3})$ samples, but there is an algorithm using $n$-qubit
quantum memory which only requires $O(n)$ samples.
The separations we show are sufficiently large and could already be evident,
for instance, with tens of qubits. This provides a concrete path towards
demonstrating real-world advantage for learning algorithms with quantum memory.
Related papers
- The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$.
In particular, we design global protocols for small set expansion, unique games, and PCP verification.
We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
arXiv Detail & Related papers (2024-02-29T01:35:46Z) - 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) - Non-Linear Transformations of Quantum Amplitudes: Exponential
Improvement, Generalization, and Applications [0.0]
Quantum algorithms manipulate the amplitudes of quantum states to find solutions to computational problems.
We present a framework for applying a general class of non-linear functions to the amplitudes of quantum states.
Our work provides an important and efficient building block with potentially numerous applications in areas such as optimization, state preparation, quantum chemistry, and machine learning.
arXiv Detail & Related papers (2023-09-18T14:57:21Z) - Fundamental causal bounds of quantum random access memories [13.19534468575575]
We study the intrinsic bounds of rapid quantum memories based on causality.
We show that QRAM can accommodate up to $mathcalO(107)$ logical qubits in 1 dimension, $mathcalO(1015)$ to $mathcalO(1020)$ in various 2D architectures, and $mathcalO(1024)$ in 3 dimensions.
arXiv Detail & Related papers (2023-07-25T12:40:48Z) - Quantivine: A Visualization Approach for Large-scale Quantum Circuit
Representation and Analysis [31.203764035373677]
We develop Quantivine, an interactive system for exploring and understanding quantum circuits.
A series of novel circuit visualizations are designed to uncover contextual details such as qubit provenance, parallelism, and entanglement.
The effectiveness of Quantivine is demonstrated through two usage scenarios of quantum circuits with up to 100 qubits.
arXiv Detail & Related papers (2023-07-18T04:51:28Z) - Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid
Memory [9.615949949517901]
We prove that any quantum algorithm with both, classical memory and quantum memory, requires either $Omega(n2)$ bits of classical memory or $Omega(n)$ bits of quantum memory or an exponential number of samples.
Our results refute the possibility that a small amount of quantum memory significantly reduces the size of classical memory needed for efficient learning on these problems.
arXiv Detail & Related papers (2023-03-01T03:22:26Z) - $T$-depth-optimized Quantum Search with Quantum Data-access Machine [0.0]
We introduce an efficient quantum data-access process, dubbed as quantum data-access machine (QDAM)
We analyze the runtime of our algorithm in view of the fault-tolerant quantum computation (FTQC) consisting of logical qubits within an effective quantum error correction code.
arXiv Detail & Related papers (2022-11-08T01:36:02Z) - 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) - 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) - 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) - Quantum Coupon Collector [62.58209964224025]
We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements.
We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
arXiv Detail & Related papers (2020-02-18T16:14:55Z)
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.