Quantum Computing and Dynamical Quantum Models

2002/05/11 by Scott Aaronson, Aaronson, Scott
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0205059

6 pages, submitted to PRL

arxiv created 2002/05/11 · openalex publication_date 2002/05/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A dynamical quantum model assigns an eigenstate to a specified observable even when no measurement is made, and gives a stochastic evolution rule for that eigenstate. Such a model yields a distribution over classical histories of a quantum state. We study what can be computed by sampling from that distribution, i.e., by examining an observer's entire history. We show that, relative to an oracle, one can solve problems in polynomial time that are intractable even for quantum computers; and can search an N-element list in order N^1/3 steps (though not fewer).

Related

• Quantum Computing and Information Extraction for Dynamical Quantum Systems
• A Quantum Algorithm to Efficiently Sample from Interfering Binary Trees
• Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories
• Use of Quantum Sampling to Calculate Mean Values of Observables and Partition Function of a Quantum System
• Quantum Gibbs Sampling Using Szegedy Operators