The copy complexity for distributed quantum state certification under limited classical and quantum communication is tightly characterized: public-coin protocols achieve Θ(d²/(2^{n_q}2^{n_c/2}ε²)), while private-coin protocols require Ω(d³/(4^{n_q}2^{n_c}ε²)).
Testing and learning structured quantum Hamiltonians
7 Pith papers cite this work. Polarity classification is still indexing.
7
Pith papers citing it
abstract
We consider the problems of testing and learning an unknown $n$-qubit Hamiltonian $H$ from queries to its evolution operator $e^{-iHt}$ under the normalized Frobenius norm. We prove: 1. Local Hamiltonians: We give a tolerant testing protocol to decide if $H$ is $\epsilon_1$-close to $k$-local or $\epsilon_2$-far from $k$-local, with $O(1/(\epsilon_2-\epsilon_1)^{4})$ queries, solving open questions posed in a recent work by Bluhm et al. For learning a $k$-local $H$ up to error $\epsilon$, we give a protocol with query complexity $\exp(O(k^2+k\log(1/\epsilon)))$ independent of $n$, by leveraging the non-commutative Bohnenblust-Hille inequality. 2. Sparse Hamiltonians: We give a protocol to test if $H$ is $\epsilon_1$-close to being $s$-sparse (in the Pauli basis) or $\epsilon_2$-far from being $s$-sparse, with $O(s^{6}/(\epsilon_2^2-\epsilon_1^2)^{6})$ queries. For learning up to error $\epsilon$, we show that $O(s^{4}/\epsilon^{8})$ queries suffice. 3. Learning without memory: The learning results stated above have no dependence on $n$, but require $n$-qubit quantum memory. We give subroutines that allow us to learn without memory; increasing the query complexity by a $(\log n)$-factor in the local case and an $n$-factor in the sparse case. 4. Testing without memory: We give a new subroutine called Pauli hashing, which allows one to tolerantly test $s$-sparse Hamiltonians with $O(s^{14}/(\epsilon_2^2-\epsilon_1^2)^{18})$ queries. A key ingredient is showing that $s$-sparse Pauli channels can be tolerantly tested under the diamond norm with $O(s^2/(\epsilon_2-\epsilon_1)^6)$ queries. Along the way, we prove new structural theorems for local and sparse Hamiltonians. We complement our learning results with polynomially weaker lower bounds. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms in the support of the Pauli spectrum.
fields
quant-ph 7representative citing papers
Forward-only Hamiltonian certification and locality testing require Theta(min(1/epsilon^p, d^(1-1/p)/epsilon)) total evolution time, versus Theta(min(1/epsilon^(p/2), d^(1/2-1/p)/epsilon)) with time reversal, for every normalized Schatten p-norm.
Near-optimal certification of quantum Ising Hamiltonians from time evolution, plus sample-efficient learning and certification of their Gibbs states.
A new algorithm and lower bound tightly determine the total evolution time needed to test whether a Hamiltonian is local or far from local.
A provable exponential quantum-classical learning separation is established for predicting expectation values of time-evolved quantum states under unknown low-intersection Hamiltonians, assuming BQP ⊄ P/poly.
A refined Bell-sampling analysis reduces sparse Hamiltonian learning to near-linear evolution time and produces a faster Hamiltonian sparsity test, both using only forward time evolution.
citing papers explorer
-
Distributed Quantum Property Testing with Quantum Carrier Pigeons
The copy complexity for distributed quantum state certification under limited classical and quantum communication is tightly characterized: public-coin protocols achieve Θ(d²/(2^{n_q}2^{n_c/2}ε²)), while private-coin protocols require Ω(d³/(4^{n_q}2^{n_c}ε²)).
-
The power of time reversal in Hamiltonian property testing
Forward-only Hamiltonian certification and locality testing require Theta(min(1/epsilon^p, d^(1-1/p)/epsilon)) total evolution time, versus Theta(min(1/epsilon^(p/2), d^(1/2-1/p)/epsilon)) with time reversal, for every normalized Schatten p-norm.
-
Certifying and learning quantum Ising Hamiltonians
Near-optimal certification of quantum Ising Hamiltonians from time evolution, plus sample-efficient learning and certification of their Gibbs states.
-
Hamiltonian Locality Testing via Trotterized Postselection
A new algorithm and lower bound tightly determine the total evolution time needed to test whether a Hamiltonian is local or far from local.
-
Provable learning separation for predicting time-evolution of quantum many-body systems
A provable exponential quantum-classical learning separation is established for predicting expectation values of time-evolved quantum states under unknown low-intersection Hamiltonians, assuming BQP ⊄ P/poly.
-
Improved Hamiltonian learning and sparsity testing through Bell sampling
A refined Bell-sampling analysis reduces sparse Hamiltonian learning to near-linear evolution time and produces a faster Hamiltonian sparsity test, both using only forward time evolution.
- Hamiltonian Learning at Scale