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.

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

References in corpus (49)

• Fault-tolerant quantum computation by anyons
• Elementary gates for quantum computation
• Black holes as mirrors: quantum information in random subsystems
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Quantum state tomography via compressed sensing
• Quantum control theory and applications: A survey
• Universal blind quantum computation
• Towards the fast scrambling conjecture
• Everything You Always Wanted to Know About LOCC (But Were Afraid to Ask)
• Quantum Circuits Architecture
• Sub-millihertz magnetic spectroscopy with a nanoscale quantum sensor
• Quantum Tomography via Compressed Sensing: Error Bounds, Sample Complexity, and Efficient Estimators
• Non-Markovian quantum processes: complete framework and efficient characterisation
• Quantum state discrimination and its applications
• Random Quantum Circuits are Approximate 2-designs
• Improved quantum metrology using quantum error-correction
• Quantum Error Correction for Metrology
• Unconditionally verifiable blind computation
• Information-theoretic bounds on quantum advantage in machine learning
• Virtual Distillation for Quantum Error Mitigation
• Increasing sensing resolution with error correction
• Sample-optimal tomography of quantum states
• Verification of quantum computation: An overview of existing approaches
• The quantum query complexity of the hidden subgroup problem is polynomial
• Experimental quantum compressed sensing for a seven-qubit system
• Experimental verification of quantum computations
• Quantum Hamiltonian Complexity
• Quantum Overlapping Tomography
• Toward a general theory of quantum games
• Pseudorandom States, Non-Cloning Theorems and Quantum Money
• Quantum circuits cannot control unknown operations
• Adaptive versus non-adaptive strategies for quantum channel discrimination
• Fast-forwarding of Hamiltonians and Exponentially Precise Measurements
• Quantum lithography, entanglement and Heisenberg-limited parameter estimation
• Reversing Unknown Quantum Transformations: Universal Quantum Circuit for Inverting General Unitary Operations
• Hamiltonian Tomography via Quantum Quench
• Superdensity Operators for Spacetime Quantum Mechanics
• Probabilistic exact universal quantum circuits for transforming unitary operations
• Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
• Weingarten calculus for matrix ensembles associated with compact symmetric spaces
• Spectral decoupling in many-body quantum chaos
• Heisenberg limited metrology using Quantum Error-Correction Codes
• Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
• Approximating Fractional Time Quantum Evolution
• Scalable Bayesian Hamiltonian learning
• Controlled quantum operations and combs, and their applications to universal controllization of divisible unitary operations
• Sample efficient tomography via Pauli Measurements
• Oracle complexity classes and local measurements on physical Hamiltonians
• Weingarten calculus via orthogonality relations: new applications

Cited by in corpus (31)

• 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
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• 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
• What the foundations of quantum computer science teach us about chemistry
• Entanglement island, miracle operators and the firewall
• Quantum advantage for noisy channel discrimination
• Inferring physical properties of symmetric states from the fewest copies
• 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
• Quantum Kerr Learning
• Toward Instance-Optimal State Certification With Incoherent Measurements
• 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