A Quantum Query Complexity Trichotomy for Regular Languages

Representations of events in nerve nets and finite automata

Stephen Cole Kleene · 1956

Earlier work this paper cites.

Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines

Kenneth Krohn and John Rhodes · 1965

Earlier work this paper cites.

On finite monoids having only trivial subgroups

Marcel Paul Schützenberger · 1965

Earlier work this paper cites.

Hierarchies of memory limited computations

Richard Edwin Stearns, Juris Hartmanis, and Philip M Lewis · 1965

Earlier work this paper cites.

Tense logic and the theory of linear order

Johan Anthony Wilem Kamp · 1968

Earlier work this paper cites.

Counter-Free Automata (MIT research monograph no. 65)

Robert McNaughton and Seymour A Papert · 1971

Earlier work this paper cites.

Automata, Languages, and Machines

Samuel Eilenberg · 1974

Earlier work this paper cites.

Some simplified 𝖭𝖯 {\mathsf{NP}} -complete problems

Michael R Garey, David S Johnson, and Larry Stockmeyer · 1974

Earlier work this paper cites.

Noncounting context-free languages

Stefano Crespi-Reghizzi, Giovanni Guida, and Dino Mandrioli · 1978

Earlier work this paper cites.

Universality considerations in VLSI circuits

Leslie G Valiant · 1981

Earlier work this paper cites.

Unbounded fan-in circuits and associative functions

Ashok K Chandra, Steven Fortune, and Richard Lipton · 1983

Cited alongside, same era.

A tight Ω ⁡ ( log ⁡ log ⁡ n ) {\Omega}(\log\log n) -bound on the time for parallel RAM’s to compute nondegenerated boolean functions

Hans-Ulrich Simon · 1983

Cited alongside, same era.

Finite monoids and the fine structure of 𝖭𝖢 1 {\mathsf{NC}}^{1}

David A Barrington and Denis Thérien · 1988

Cited alongside, same era.

Regular languages are testable with a constant number of queries

Noga Alon, Michael Krivelevich, Ilan Newman, and Mario Szegedy · 2001

Cited alongside, same era.

Quantum lower bounds by polynomials

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf · 2001

Cited alongside, same era.

Quantum lower bounds by quantum arguments

Andris Ambainis · 2002

Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range

Andris Ambainis · 2005

Later among the works it cites.

Quantum lower bound for the collision problem with small range

Samuel Kutin · 2005

Later among the works it cites.

Introduction to the Theory of Computation

Michael Sipser · 2006

Later among the works it cites.

Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function

Ben W Reichardt · 2009

Later among the works it cites.

Quantum query complexity of minor-closed graph properties

Andrew M Childs and Robin Kothari · 2012

Later among the works it cites.

Circuit complexity of properties of graphs with constant planar cutwidth

Kristoffer Arnsfelt Hansen, Balagopal Komarath, Jayalal Sarma, Sven Skyum, and Navid Talebanfard · 2014