Articles under category:
Quantum Computing
ToC Library Graduate Surveys 7 (2016) 81 pages
A Survey of Quantum Property Testing
by Ashley Montanaro and Ronald de Wolf
ToC Library Graduate Surveys 2 (2011) 54 pages
Quantum Proofs for Classical Theorems
by Andrew Drucker and Ronald de Wolf
Vol 18, Article 17 (pp 1-11) [NOTE]
A Stochastic Calculus Approach to the Oracle Separation of $\mathsf{BQP}$ and $\mathsf{PH}$
by Xinyu Wu
Vol 18, Article 11 (pp 1-49)
Span Programs and Quantum Space Complexity
by Stacey Jeffery
Vol 16, Article 11 (pp 1-8) [NOTE]
On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
by Scott Aaronson and Sam Gunn
Vol 16, Article 10 (pp 1-71)
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
by Mark Bun, Robin Kothari, and Justin Thaler
Vol 15, Article 5 (pp 1-42)
Classical Verification of Quantum Proofs
by Zhengfeng Ji
Vol 14, Article 15 (pp 1-24)
Quantum-Walk Speedup of Backtracking Algorithms
by Ashley Montanaro
Vol 14, Article 11 (pp 1-37)
How to Verify a Quantum Computation
by Anne Broadbent
Vol 14, Article 7 (pp 1-45)
Quantum Homomorphic Encryption for Polynomial-Size Circuits
by Yfke Dulek, Christian Schaffner, and Florian Speelman
Vol 14, Article 1 (pp 1-27)
Linear-Time Algorithm for Quantum 2SAT
by Itai Arad, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang
Vol 12, Article 18 (pp 1-35)
Upper Bounds on Quantum Query Complexity Inspired by the Elitzur--Vaidman Bomb Tester
by Cedric Yen-Yu Lin and Han-Hsuan Lin
Vol 12, Article 16 (pp 1-34)
Dual Polynomials for Collision and Element Distinctness
by Mark Bun and Justin Thaler
Vol 12, Article 3 (pp 1-42)
Interactive Proofs for $\mathsf{BQP}$ via Self-Tested Graph States
by Matthew McKague
Vol 11, Article 20 (pp 491-603)
The Bose-Hubbard Model is QMA-complete
by Andrew M. Childs, David Gosset, and Zak Webb
Vol 11, Article 16 (pp 403-412) [NOTE]
Quantum Algorithm for Monotonicity Testing on the Hypercube
by Aleksandrs Belovs and Eric Blais
Vol 11, Article 6 (pp 183-219)
How Hard Is It to Approximate the Jones Polynomial?
by Greg Kuperberg
Vol 11, Article 3 (pp 59-103)
Quantum Interactive Proofs and the Complexity of Separability Testing
by Gus Gutoski, Patrick Hayden, Kevin Milner, and Mark M. Wilde
Vol 10, Article 6 (pp 133-166)
The Need for Structure in Quantum Speedups
by Scott Aaronson and Andris Ambainis
Vol 9, Article 26 (pp 809-843)
On Beating the Hybrid Argument
by Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola
Vol 9, Article 9 (pp 349-401)
Quantum Money from Hidden Subspaces
by Scott Aaronson and Paul Christiano
Vol 9, Article 4 (pp 143-252)
The Computational Complexity of Linear Optics
by Scott Aaronson and Alex Arkhipov
Vol 9, Article 2 (pp 31-116)
The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
by Daniel Gottesman and Sandy Irani
Vol 8, Article 27 (pp 623-645)
Near-Optimal and Explicit Bell Inequality Violations
by Harry Buhrman, Oded Regev, Giannicola Scarpa, and Ronald de Wolf
Vol 8, Article 21 (pp 461-486)
Two-Source Extractors Secure Against Quantum Adversaries
by Roy Kasher and Julia Kempe
Vol 8, Article 17 (pp 375-400)
On the Power of a Unique Quantum Witness
by Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, and Shengyu Zhang
Vol 8, Article 16 (pp 369-374) [NOTE]
Quantum Private Information Retrieval with Sublinear Communication Complexity
by François Le Gall
Vol 8, Article 13 (pp 291-319)
Span-Program-Based Quantum Algorithm for Evaluating Formulas
by Ben Reichardt and Robert Špalek
Vol 8, Article 1 (pp 1-51)
Time-Space Efficient Simulations of Quantum Computations
by Dieter van Melkebeek and Thomas Watson
Vol 7, Article 7 (pp 101-117)
Quantum Interactive Proofs with Short Messages
by Salman Beigi, Peter Shor, and John Watrous
Vol 7, Article 2 (pp 19-25) [NOTE]
Inverting a Permutation is as Hard as Unordered Search
by Ashwin Nayak
Vol 6, Article 3 (pp 47-79)
Quantum Expanders: Motivation and Construction
by Avraham Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma
Vol 6, Article 1 (pp 1-25)
A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search
by Andris Ambainis
Vol 5, Article 11 (pp 217-238)
Semidefinite Programs for Completely Bounded Norms
by John Watrous
Vol 5, Article 8 (pp 141-172)
Parallel Repetition: Simplification and the No-Signaling Case
by Thomas Holenstein
Vol 5, Article 5 (pp 119-123) [NOTE]
Discrete-Query Quantum Algorithm for NAND Trees
by Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo
Vol 5, Article 1 (pp 1-42)
The Power of Unentanglement
by Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor
Vol 4, Article 8 (pp 169-190)
A Quantum Algorithm for the Hamiltonian NAND Tree
by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann
Vol 4, Article 3 (pp 53-76)
Derandomizing the Ahlswede-Winter matrix-valued Chernoff bound using pessimistic estimators, and applications
by Avi Wigderson and David Xiao
Vol 3, Article 7 (pp 129-157)
Quantum Versus Classical Proofs and Advice
by Scott Aaronson and Greg Kuperberg
Vol 3, Article 4 (pp 61-79)
A Simple PromiseBQP-complete Matrix Problem
by Dominik Janzing and Pawel Wocjan
Vol 2, Article 1 (pp 1-18)
All Quantum Adversary Methods are Equivalent
by Robert Špalek and Mario Szegedy
Vol 1, Article 5 (pp 81-103)
Quantum Fan-out is Powerful
by Peter Høyer and Robert Špalek
Vol 1, Article 4 (pp 47-79)
Quantum Search of Spatial Regions
by Scott Aaronson and Andris Ambainis
Vol 1, Article 3 (pp 37-46)
Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
by Andris Ambainis
Vol 1, Article 2 (pp 29-36)
Quantum Lower Bound for the Collision Problem with Small Range
by Samuel Kutin
Vol 1, Article 1 (pp 1-28)
Limitations of Quantum Advice and One-Way Communication
by Scott Aaronson