Learning Quantum Processes with Quantum Statistical Queries
arXiv:2310.02075 · doi:10.22331/q-2025-05-12-1739
Abstract
In this work, we initiate the study of learning quantum processes from quantum statistical queries. We focus on two fundamental learning tasks in this new access model: shadow tomography of quantum processes and process tomography with respect to diamond distance. For the former, we present an efficient average-case algorithm along with a nearly matching lower bound with respect to the number of observables to be predicted. For the latter, we present average-case query complexity lower bounds for learning classes of unitaries. We obtain an exponential lower bound for learning unitary 2-designs and a doubly exponential lower bound for Haar-random unitaries. Finally, we demonstrate the practical relevance of our access model by applying our learning algorithm to attack an authentication protocol using Classical-Readout Quantum Physically Unclonable Functions, partially addressing an important open question in quantum hardware security.
32 pages, 2 figures. Corrected proofs and improved presentation. Accepted in Quantum
References in corpus (39)
- An introduction to quantum machine learning
- Predicting Many Properties of a Quantum System from Very Few Measurements
- An adaptive variational algorithm for exact molecular simulations on a quantum computer
- Quantum Process Tomography: Resource Analysis of Different Strategies
- Demonstration of qubit operations below a rigorous fault tolerance threshold with gate set tomography
- The randomized measurement toolbox
- Breaking Symmetric Cryptosystems using Quantum Period Finding
- Information-theoretic bounds on quantum advantage in machine learning
- Provably efficient machine learning for quantum many-body problems
- Hamiltonian Learning and Certification Using Quantum Resources
- Efficient learning of quantum noise
- Efficient estimation of Pauli observables by derandomization
- Multiqubit Clifford groups are unitary 3-designs
- Efficient quantum measurement of Pauli operators in the presence of finite sampling error
- Quantum noise protects quantum classifiers against adversaries
- Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
- Optimizing quantum process tomography with unitary 2-designs
- Quantum PUF for Security and Trust in Quantum Computing
- Improved Bounds on Quantum Learning Algorithms
- Quantum Physical Unclonable Functions: Possibilities and Impossibilities
- Overlapped grouping measurement: A unified framework for measuring quantum states
- Shadow process tomography of quantum channels
- Classical Shadows for Quantum Process Tomography on Near-term Quantum Computers
- Learning with Errors is easy with quantum samples
- Spectral measures of powers of random matrices
- Unforgeable Quantum Encryption
- Learning and Testing Algorithms for the Clifford Group
- Optimal quantum tomography
- Learning quantum circuits of some gates
- Improved spectral gaps for random quantum circuits: large local dimensions and all-to-all interactions
- A single -gate makes distribution learning hard
- Client-Server Identification Protocols with Quantum PUF
- Query-optimal estimation of unitary channels in diamond distance
- Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
- Learning Classical Readout Quantum PUFs based on single-qubit gates
- On the Hardness of PAC-learning Stabilizer States with Noise
- On the Pauli Spectrum of QAC0
- Quantum Learning Boolean Linear Functions w.r.t. Product Distributions
- Classical Verification of Quantum Learning