|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Exponential separations between learning with and without quantum memory | | Sitan Chen
; Jordan Cotler
; Hsin-Yuan Huang
; Jerry Li
; | | Date: |
10 Nov 2021 | | 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. | | Source: | arXiv, 2111.05881 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER