Learning unitaries with quantum statistical queries

Abstract

We propose several algorithms for learning unitary operators from quantum statistical queries with respect to their Choi-Jamiolkowski state. Quantum statistical queries capture the capabilities of a learner with limited quantum resources, which receives as input only noisy estimates of expected values of measurements. Our approach leverages quantum statistical queries to estimate the Fourier mass of a unitary on a subset of Pauli strings, generalizing previous techniques developed for uniform quantum examples. Specifically, we show that the celebrated quantum Goldreich-Levin algorithm can be implemented with quantum statistical queries, whereas the prior version of the algorithm involves oracle access to the unitary and its inverse. As an application, we prove that quantum Boolean functions with constant total influence or with constant degree are efficiently learnable in our model. Moreover, we prove that $\mathcal{O}(\log n)$-juntas are efficiently learnable and constant-depth circuits are learnable query-efficiently with quantum statistical queries. On the other hand, all previous algorithms for these tasks demand significantly greater resources, such as oracle access to the unitary or direct access to the Choi-Jamiolkowski state. We also demonstrate that, despite these positive results, quantum statistical queries lead to an exponentially larger query complexity for certain tasks, compared to separable measurements to the Choi-Jamiolkowski state. In particular, we show an exponential lower bound for learning a class of phase-oracle unitaries and a double exponential lower bound for testing the unitarity of channels. Taken together, our results indicate that quantum statistical queries offer a unified framework for various unitary learning tasks, with potential applications in quantum machine learning, many-body physics and benchmarking of near-term devices.

40 pages

References in corpus (26)

• Direct Fidelity Estimation from Few Pauli Measurements
• Anomalous thermalization in ergodic systems
• Supervised quantum machine learning models are kernel methods
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Shadows of quantum machine learning
• Density dynamics in translationally invariant spin-1/2 chains at high temperatures: a current auto-correlation approach to finite time- and length-scales
• Real-time dynamics at finite temperature by DMRG: A path-integral approach
• Classical surrogates for quantum learning models
• Quantum Algorithms for Learning and Testing Juntas
• Learning and Testing Algorithms for the Clifford Group
• Learning quantum states and unitaries of bounded gate complexity
• A single $T$-gate makes distribution learning hard
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
• Learning shallow quantum circuits
• Noncommutative Bohnenblust--Hille inequalities
• On the Pauli Spectrum of QAC0
• Efficient distributed inner product estimation via Pauli sampling
• A polynomial-time classical algorithm for noisy quantum circuits
• Classically Approximating Variational Quantum Machine Learning with Random Fourier Features
• Learning marginals suffices!
• Ergodicity, eigenstate thermalization, and the foundations of statistical mechanics in quantum and classical systems
• Learning Quantum Processes with Quantum Statistical Queries
• Thermalization rates and quantum Ruelle-Pollicott resonances: insights from operator hydrodynamics
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms
• Learning shallow quantum circuits with many-qubit gates
• On the sample complexity of purity and inner product estimation

Cited by in corpus (3)

• Lie-algebraic classical simulations for quantum computing
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes
• Agnostic Process Tomography