Quantum Algorithmic Measurement

Abstract

We initiate the systematic study of experimental quantum physics from the perspective of computational complexity. To this end, we define the framework of quantum algorithmic measurements (QUALMs), a hybrid of black box quantum algorithms and interactive protocols. We use the QUALM framework to study two important experimental problems in quantum many-body physics: determining whether a system's Hamiltonian is time-independent or time-dependent, and determining the symmetry class of the dynamics of the system. We study abstractions of these problem and show for both cases that if the experimentalist can use her experimental samples coherently (in both space and time), a provable exponential speedup is achieved compared to the standard situation in which each experimental sample is accessed separately. Our work suggests that quantum computers can provide a new type of exponential advantage: exponential savings in resources in quantum experiments.

77+19 pages, 11 figures; v2: improved introduction, typos fixed, references added

References in corpus (12)

• Black holes as mirrors: quantum information in random subsystems
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Quantum Circuits Architecture
• Sub-millihertz magnetic spectroscopy with a nanoscale quantum sensor
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Quantum state discrimination and its applications
• Information-theoretic bounds on quantum advantage in machine learning
• Virtual Distillation for Quantum Error Mitigation
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• Approximating Fractional Time Quantum Evolution
• Scalable Bayesian Hamiltonian learning
• Sample efficient tomography via Pauli Measurements

Cited by in corpus (30)

• Quantum advantage in learning from experiments
• Generalization in quantum machine learning from few training data
• Information-theoretic bounds on quantum advantage in machine learning
• Group-Invariant Quantum Machine Learning
• Scalable measures of magic resource for quantum computers
• Classical Shadow Tomography with Locally Scrambled Quantum Dynamics
• Learning many-body Hamiltonians with Heisenberg-limited scaling
• Out-of-distribution generalization for learning quantum dynamics
• Subtleties in the trainability of quantum machine learning models
• Statistical Methods for Quantum State Verification and Fidelity Estimation
• Analytic theory for the dynamics of wide quantum neural networks
• Quantum advantages for Pauli channel estimation
• Improved machine learning algorithm for predicting ground state properties
• Distributed quantum inner product estimation
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
• Entanglement island, miracle operators and the firewall
• What the foundations of quantum computer science teach us about chemistry
• Inferring physical properties of symmetric states from the fewest copies
• Quantum advantage for noisy channel discrimination
• Unitarity estimation for quantum channels
• Operational Quantum Average-Case Distances
• Generative model for learning quantum ensemble via optimal transport loss
• Cross-Platform Verification in Quantum Networks
• A Hierarchy for Replica Quantum Advantage
• Toward Instance-Optimal State Certification With Incoherent Measurements
• Quantum Kerr Learning
• Lower Bounds for Learning Quantum States with Single-Copy Measurements
• Stable many-body resonances in open quantum systems
• Quantum Proofs of Proximity
• Revisiting dequantization and quantum advantage in learning tasks