Fetching the paper…
Reading the bibliography…
Space complexity is a key field of study in theoretical computer science.
Relationships between nondeterministic and deterministic tape complexities
Walter J Savitch · 1970
Earlier work this paper cites.
Quantum theory, the church–turing principle and the universal quantum computer
David Deutsch · 1985
Earlier work this paper cites.
Nondeterministic space is closed under complementation
Neil Immerman · 1988
Earlier work this paper cites.
The method of forced enumeration for nondeterministic automata
Róbert Szelepcsényi · 1988
Earlier work this paper cites.
Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1
David A. Mix Barrington · 1989
Earlier work this paper cites.
Computing algebraic formulas using a constant number of registers
Michael Ben-Or and Richard Cleve · 1992
Earlier work this paper cites.
Quantum circuit complexity
Andrew Chi-Chih Yao · 1993
Earlier work this paper cites.
Quantum complexity theory
Ethan Bernstein and Umesh Vazirani · 1997
Earlier work this paper cites.
Quantum computations: algorithms and error correction
A Yu Kitaev · 1997
Earlier work this paper cites.
Power of one bit of quantum information
E. Knill and R. Laflamme · 1998
Earlier work this paper cites.
Space-bounded quantum computation
John Harrison Watrous · 1998
Earlier work this paper cites.
Quantum algorithms for solvable groups
John Watrous · 2001
Earlier work this paper cites.
Mathematical models of quantum computation
Tetsuro Nishino · 2002
Earlier work this paper cites.
Computational complexity of uniform quantum circuit families and quantum turing machines
Harumichi Nishimura and Masanao Ozawa · 2002
Earlier work this paper cites.
Problems and results in extremal combinatorics—i
Noga Alon · 2003
Earlier work this paper cites.
The solovay-kitaev algorithm
Christopher M. Dawson and Michael A. Nielsen · 2006
Earlier work this paper cites.
Computation with unitaries and one pure qubit, 2006
Dan Shepherd · 2006
Cited alongside, same era.
Estimating jones polynomials is a complete problem for one clean qubit, 2008
Peter W. Shor and Stephen P. Jordan · 2008
Cited alongside, same era.
Perfect computational equivalence between quantum turing machines and finitely generated uniform quantum circuit families
Harumichi Nishimura and Masanao Ozawa · 2009
Cited alongside, same era.
Matchgate and space-bounded quantum computations are equivalent
Richard Jozsa, Barbara Kraus, Akimasa Miyake, and John Watrous · 2010
Cited alongside, same era.
Quantum Computation and Quantum Information (10th Anniversary edition)
Michael A. Nielsen and Isaac L. Chuang · 2010
Cited alongside, same era.
Inverting well conditioned matrices in quantum logspace
Amnon Ta-Shma · 2013
Catalytic embeddings of quantum circuits
Matthew Amy, Matthew Crawford, Andrew N Glaudell, Melissa L Macasieb, Samuel S Mendelson, and Neil J Ross · 2023
Later among the works it cites.
How many non-orthogonal vectors fit into a complex vector space?
Dustin G. Mixon (https://mathoverflow.net/users/29873/dustin-g mixon) · 2023
Later among the works it cites.
Reusing space: Techniques and open problems
Ian Mertz · 2023
Later among the works it cites.
Sagar Bisoyi, Krishnamoorthy Dinesh, Bhabya Rai, and Jayalal Sarma · 2024
Later among the works it cites.
Tree evaluation is in space O ( log n ⋅ log log n ) O(\log n\cdot\log\log n)
James Cook and Ian Mertz · 2024
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Computing with a full memory: Catalytic space
Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, and Florian Speelman · 2014
Cited alongside, same era.
Catalytic space: on reversibility and multiple-access randomness
Yfke Dulek · 2015
Cited alongside, same era.
A note on amortized branching program complexity
Aaron Potechin · 2017
Cited alongside, same era.
Catalytic space: Non-determinism and hierarchy
Harry Buhrman, Michal Koucký, Bruno Loff, and Florian Speelman · 2018
Cited alongside, same era.
Randomized and symmetric catalytic computation
Samir Datta, Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari · 2020
Cited alongside, same era.
Quantum logspace algorithm for powering matrices with bounded norm
Uma Girish, Ran Raz, and Wei Zhan · 2020
Cited alongside, same era.
Chetan Gupta, Rahul Jain, Vimal Raj Sharma, and Raghunath Tewari · 2024
Later among the works it cites.
Quantum logspace computations are verifiable
Uma Girish, Ran Raz, and Wei Zhan · 2024
Later among the works it cites.
Catalysis in quantum information theory
Patryk Lipka-Bartosik, Henrik Wilming, and Nelly HY Ng · 2024
Later among the works it cites.
Catalytic computing and register programs beyond log-depth
Yaroslav Alekseev, Yuval Filmus, Ian Mertz, Alexander Smal, and Antoine Vinciguerra · 2025
Closest in time.
Bipartite matching is in catalytic logspace
Aryan Agarwala and Ian Mertz · 2025
Closest in time.
The structure of catalytic space: Capturing randomness and time via compression
James Cook, Jiatu Li, Ian Mertz, and Edward Pyne · 2025
Closest in time.
Fully characterizing lossy catalytic computation
Marten Folkertsma, Ian Mertz, Florian Speelman, and Quinten Tupker · 2025
Closest in time.
Collapsing catalytic classes
Michal Koucký, Ian Mertz, Ted Pyne, and Sasha Sami · 2025
Closest in time.
Catalytic communication
Edward Pyne, Nathan S. Sheffield, and William Wang · 2025
Closest in time.
Simulating time in square-root space
Ryan Williams · 2025
Closest in time.