Articles under category:
Quantum Computing
Quantum Computing
ToC Library Graduate Surveys 7 (2016) 81 pages
A Survey of Quantum Property Testing
by Ashley Montanaro and Ronald de Wolf
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
Quantum Proofs for Classical Theorems
by Andrew Drucker and Ronald de Wolf
Vol 21, Article 1 (pp 1-28)
On Linear-Algebraic Notions of Expansion
by Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, and Chuanqi Zhang
On Linear-Algebraic Notions of Expansion
by Yinan Li, Youming Qiao, Avi Wigderson, Yuval Wigderson, and Chuanqi Zhang
Vol 20, Article 3 (pp 1-87)
Verifier-on-a-Leash: New Schemes for Verifiable Delegated Quantum Computation, with Quasilinear Resources
by Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery, and Thomas Vidick
Verifier-on-a-Leash: New Schemes for Verifiable Delegated Quantum Computation, with Quasilinear Resources
by Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery, and Thomas Vidick
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
A Stochastic Calculus Approach to the Oracle Separation of $\mathsf{BQP}$ and $\mathsf{PH}$
by Xinyu Wu
Vol 16, Article 11 (pp 1-8)
[NOTE]
On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking
by Scott Aaronson and Sam Gunn
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
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
by Mark Bun, Robin Kothari, and Justin Thaler
Vol 14, Article 7 (pp 1-45)
Quantum Homomorphic Encryption for Polynomial-Size Circuits
by Yfke Dulek, Christian Schaffner, and Florian Speelman
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search
by Andris Ambainis
Vol 5, Article 8 (pp 141-172)
Parallel Repetition: Simplification and the No-Signaling Case
by Thomas Holenstein
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
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
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
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
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
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
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
All Quantum Adversary Methods are Equivalent
by Robert Špalek and Mario Szegedy
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
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
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
Limitations of Quantum Advice and One-Way Communication
by Scott Aaronson