2007/12/15 by Dieter van Melkebeek, van Melkebeek, Dieter, Thomas Watson +1 · 1 citation
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.0712.2545
25 pages
arxiv created 2007/12/15 · openalex publication_date 2007/12/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We obtain the first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability. Our bound applies to MajSAT and MajMajSAT, which are complete problems for the first and second levels of the counting hierarchy, respectively. We prove that for every real d and every positive real epsilon there exists a real c>1 such that either: MajMajSAT does not have a quantum algorithm with bounded two-sided error that runs in time nc, or MajSAT does not have a quantum algorithm with bounded two-sided error that runs in time nd and space n1-ε. In particular, MajMajSAT cannot be solved by a quantum algorithm with bounded two-sided error running in time n1+o(1) and space n1-ε for any epsilon>0. The key technical novelty is a time- and space-efficient simulation of quantum computations with intermediate measurements by probabilistic machines with unbounded error. We also develop a model that is particularly suitable for the study of general quantum computations with simultaneous time and space bounds. However, our arguments hold for any reasonable uniform model of quantum computation.