Lower Bounds on the Running Time of Two-Way Quantum Finite Automata and Sublogarithmic-Space Quantum
summary
Proves concrete limits: gives a general lower bound on 2QCFA running time in terms of Dwork–Stockmeyer non-regularity D_L, shows palindrome needs exponential time on any 2QCFA (so Ambainis–Watrous’s exponential upper bound is tight), and shows any quantum machine using o(log n) space cannot decide palindrome even with time 2^{n^{1−ε}}. Key tool is a quantum analogue of Hennie’s crossing sequences using density operators and transfer operators (quantum channels) to relate few visits to similar behavior and force large time.
AI-written summary · about
chapters (9)
- 0:00Intro
- 1:16This Paper: Tight Limitations on Quantum Advantage in the Small Space Setting
- 4:14Constant Space: Finite Automata
- 10:38Key Tool: Crossing Sequences
- 11:40DTM Crossing Sequence
- 19:362QCFA Probabilistic Computation Tree
- 21:372QCFA Stopping Ensemble
- 25:172QCFA Crossing Sequence
- 26:56Lower Bound on Running Time
related talks
18mQuantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
58mLimitations for Quantum PCPs
28mConcentration bounds for quantum states and limitations on the QAOA from polynomial approximations
22mQuantum space, ground space traversal, and how to embed multi-prover...
20mQuantum Assertion Testing Without Mid-Circuit Measurement: Strategies and Lower Bounds
33mA lower bound on the space overhead of fault-tolerant quantum computation
53mFundamental limits to quantum computation
01h 01mWhat Is "Quantum" About Quantum Computing?