Quantum Algorithmic Measurement

The paper poses the question of how to model and analyze physical experiments within a rigorous computational framework. Motivated by the growing integration of quantum computational tools in laboratory practice, the authors argue that experiments can be viewed as general quantum processes aimed at computing classical functions of physical systems to extract desired information. They propose studying the complexity of experiments analogously to quantum algorithms, emphasizing that experimentalists typically lack a full classical description of the system and instead have limited quantum access. The work introduces quantum algorithmic measurements (QUALMs) as a universal model for experiments, capturing hidden system degrees of freedom (Nature register), controllable lab interfaces (Lab register), and the experimentalist’s processing resources (Workspace). The goal is to characterize resource requirements and potential quantum advantages in experimental tasks, especially when coherent access is permitted.

The authors situate QUALMs relative to black-box quantum algorithms, quantum interactive protocols/strategies/combs, and recent efforts to leverage quantum computation in experimental physics. They discuss how early quantum algorithms (e.g., Simon’s algorithm) do not necessarily realize coherent experimental advantages when cast as QUALMs, since they access samples incoherently with product-state preparations and tensor-product measurements. They contrast prior works that showed only quadratic advantages or required strong non-adaptive assumptions for lower bounds, and note examples where exponential separations were conjectured or shown under restricted models (e.g., single-register access, query-complexity-only settings for tomography or state distinction linked to hidden subgroup problems). The present work emphasizes operational efficiency (QUALM complexity) and adaptive incoherent protocols, aiming to establish proven exponential separations for physically motivated tasks within a comprehensive experimental framework.

The methodology is to formalize experiments as QUALMs—quantum circuits/protocols interacting with a tripartite system: N (Nature/hidden degrees of freedom not directly measurable), L (Lab interface that couples to N and is controllable), and W (Workspace of the experimentalist). A lab oracle models the input physical system as a superoperator acting on N⊕L with N initialized in an unknown state. Tasks specify experimental goals via a function mapping sequences of lab-oracle uses and classical controls to classical outputs, together with admissible gate sets on L⊕W capturing operational constraints (e.g., locality, geometry). A QUALM protocol compiles admissible operations and interleaves them with lab-oracle calls, with specified input/output subsets of W. The QUALM achieves a task if, for all permitted lab oracles and inputs, the output distribution matches the task’s specification within error tolerance. Complexity measures include gate complexity and the number of lab-oracle uses; the QUALM complexity of a task is the optimal such cost. The work distinguishes coherent access QUALMs (full quantum control and entangling operations between L and W during and across oracle calls) from incoherent access QUALMs (LOCC-like structure: local operations and classical communication only, with at least one complete measurement between oracle calls, no coherence maintained across uses). For proving lower bounds, general incoherent QUALMs are reduced to probabilistic mixtures of simple measurement (SM) QUALMs that iteratively: prepare a state, apply the oracle once, measure (POVM), optionally adapt settings based on past outcomes, and repeat. The authors analyze two toy tasks: (1) Fixed Unitary Problem—distinguish a time-independent random unitary (same Haar unitary each call) from a time-dependent random unitary (fresh Haar unitary each call); (2) Symmetry Distinction Problem—distinguish among symmetry classes of dynamics modeled by different lab-oracle ensembles (fixed vs fresh random vs other structured behavior). They sketch proof techniques showing that, for the fixed unitary problem, distributions over measurement transcripts under the fixed-unitary oracle are exponentially close to those under the fresh-random oracle for SM QUALMs, implying exponentially many samples are required to distinguish. Conversely, a coherent QUALM can exploit interference across multiple oracle uses (e.g., via SWAP tests on multiple outputs) to efficiently distinguish. The framework also outlines standard algorithmic primitives in the QUALM setting (subroutines, error reduction/amplification by repetition) and discusses variants of access constraints.

• Framework: Introduces QUALMs as a universal, complexity-theoretic model for quantum experiments incorporating hidden system degrees of freedom (N), controllable lab interfaces (L), and workspace (W), along with lab oracles, tasks, admissible gates, and complexity measures.
• Coherent vs incoherent access: Formalizes incoherent QUALMs as LOCC-like protocols with complete measurements between oracle uses, and coherent QUALMs as fully quantum, allowing entanglement and coherent processing across calls.
• Exponential separation (Fixed Unitary Problem): Theorem 1 states that any incoherent (even adaptive) QUALM distinguishing a fixed Haar-random unitary oracle from a freshly random Haar oracle on n qubits requires Ω(2^n) quantum complexity (i.e., exponential resources). Key steps: (i) reduction of arbitrary incoherent QUALMs to probabilistic mixtures of simple measurement QUALMs; (ii) showing the transcript distribution under the fixed-unitary oracle is exponentially close to the uniform/fresh-random case for SM QUALMs, necessitating exponentially many samples to resolve.
• Efficient coherent protocol: A coherent QUALM using interference (e.g., SWAP tests across oracle outputs) can distinguish efficiently, yielding a provable exponential speedup over incoherent access.
• Symmetry Distinction Problem: Within a toy model of symmetry identification for many-body dynamics, coherent QUALMs similarly provide exponential savings over incoherent protocols, reinforcing the generality of the advantage.
• Implication: Establishes a new type of quantum advantage—exponential savings in experimental resources when experiments can maintain and exploit coherence across system uses.

By casting experiments as computational processes with well-defined resources and access models, the paper addresses the core question of whether quantum-coherent control can fundamentally reduce experimental costs. The demonstrated exponential separations show that coherence across multiple interactions with a physical system enables interference-based strategies (such as SWAP tests) that are inaccessible to LOCC-style, measure-and-reprepare experiments. This directly informs the design of laboratory protocols for tasks like detecting time-dependence in dynamics (fixed vs randomly varying unitaries) and identifying symmetry classes, suggesting that integrating quantum computational primitives into experiments can transform feasibility and efficiency. The QUALM framework provides a common language to compare protocols, reason about lower bounds, and articulate assumptions about access and admissible operations. These results strengthen the case for extending the quantum Church–Turing thesis beyond computation to encompass general experimental procedures, positing that any physical experiment can be efficiently simulated by a QUALM with modest overhead.

The paper proposes QUALMs as a universal, complexity-theoretic framework for modeling and analyzing quantum experiments. Using this framework, the authors construct physically motivated toy tasks and prove that coherent access enables exponential resource savings over incoherent (LOCC-like) strategies, even when the latter are adaptive. In particular, the fixed unitary problem admits an efficient coherent solution while any incoherent protocol requires Ω(2^n) resources. Similar advantages are shown for a symmetry distinction task, underscoring broad applicability. The work suggests extending the quantum Church–Turing thesis to experimental procedures and motivates developing experimentally realizable coherent access protocols. Future directions include: formal universality proofs for QUALMs; tighter bounds and concrete algorithms for broader classes of experimental tasks; exploring realistic constraints (noise, limited coherence times, restricted admissible gates); and implementing prototype coherent QUALMs in laboratory settings to validate predicted advantages.

• The tasks analyzed are simplified toy abstractions of physical problems; bridging from the toy models to full, realistic experimental scenarios requires additional assumptions and engineering details.
• Several definitions and proofs are sketched with details deferred to supplementary information; rigorous treatment of all technical conditions (e.g., distributions closeness bounds, admissible gate constraints) may rely on nontrivial assumptions.
• The exponential lower bound is shown for incoherent access under the QUALM formalization; real experiments may fall between coherent and fully incoherent models, and the exact boundaries of the separation under noise and hardware constraints are not fully characterized.
• The symmetry problem statement in the main text is only roughly specified; a complete characterization and generalization to diverse symmetry classes need further development.
• Practical resource estimates (error rates, noise robustness, constant factors) and data availability are not provided in the main text.