Fetching the paper…
Reading the bibliography…
This is a set of lecture notes suitable for a Master's course on quantum computation and information from the perspective of theoretical computer science.
Quantum sparse support vector machines, 2019
S. Saeedi and T. Arodz · 1902
Earlier work this paper cites.
Quantum supremacy using a programmable superconducting processor
F. Arute, …, and J. Martinis · 1910
Earlier work this paper cites.
N-H. Chia, A. Gilyén, T. Li, H-H. Lin, E. Tang, and C. Wang · 1910
Earlier work this paper cites.
Quantum speedup for graph sparsification, cut approximation and Laplacian solving
S. Apers and R. de Wolf · 1911
Earlier work this paper cites.
QMA-hardness of consistency of local density matrices with applications to quantum zero-knowledge
A. Broadbent and A. B. Grilo · 1911
Earlier work this paper cites.
Can quantum-mechanical description of physical reality be considered complete?
A. Einstein, B. Podolsky, and N. Rosen · 1935
Earlier work this paper cites.
On computable numbers, with an application to the Entscheidungproblem
A. M. Turing · 1936
Earlier work this paper cites.
The number of two-terminal series-parallel networks
J. Riordan and C. E. Shannon · 1942
Earlier work this paper cites.
On the Einstein-Podolsky-Rosen paradox
J. S. Bell · 1964
Earlier work this paper cites.
Schwankung von Polynomen zwischen Gitterpunkten
H. Ehlich and K. Zeller · 1964
Earlier work this paper cites.
An algorithm for the machine calculation of complex Fourier series
J. W. Cooley and J. W. Tukey · 1965
Earlier work this paper cites.
A comparison of uniform approximations on an interval and a finite subset thereof
T. J. Rivlin and E. W. Cheney · 1966
Earlier work this paper cites.
On the uniform convergence of relative frequencies of events to their probabilities
V. Vapnik and A. Chervonenkis · 1968
Earlier work this paper cites.
Proposed experiment to test local hidden-variable theories
J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt · 1969
Earlier work this paper cites.
The complexity of theorem-proving procedures
S. Cook · 1971
Earlier work this paper cites.
Schnelle Multiplikation grosser Zahlen
A. Schönhage and V. Strassen · 1971
Earlier work this paper cites.
Bounds for the quantity of information transmitted by a quantum communication channel
A. S. Holevo · 1973
Earlier work this paper cites.
Universal search problems (translated from the Russian)
L. Levin · 1973
Earlier work this paper cites.
Probabilistic machines can use less running time
R. Freivalds · 1977
Earlier work this paper cites.
A method for obtaining digital signatures and public key cryptosystems
R. Rivest, A. Shamir, and L. Adleman · 1978
Earlier work this paper cites.
Computers and Intractability : A Guide to the Theory of NP-completeness
M. Garey and D. Johnson · 1979
Earlier work this paper cites.
An Introduction to the Theory of Numbers
G. H. Hardy and E. M. Wright · 1979
Earlier work this paper cites.
Some complexity questions related to distributive computing
A. C-C. Yao · 1979
Earlier work this paper cites.
Quantum generalizations of Bell’s inequality
B. S. Cirel’son · 1980
Earlier work this paper cites.
Vychislimoe i nevychislimoe (computable and noncomputable)
Y. Manin · 1980
Earlier work this paper cites.
Experimental tests of realistic local theories via Bell’s theorem
A. Aspect, Ph. Grangier, and G. Roger · 1981
Earlier work this paper cites.
Quantum mechanical Hamiltonian models of Turing machines
P. A. Benioff · 1982
Earlier work this paper cites.
Simulating physics with computers
R. Feynman · 1982
Earlier work this paper cites.
A single quantum cannot be copied
W. K. Wootters and W. H. Zurek · 1982
Earlier work this paper cites.
Canonical labeling of graphs
L. Babai and E. M. Luks · 1983
Earlier work this paper cites.
Quantum cryptography: Public key distribution and coin tossing
C. H. Bennett and G. Brassard · 1984
Earlier work this paper cites.
A theory of the learnable
L. Valiant · 1984
Earlier work this paper cites.
Quantum theory, the Church-Turing principle, and the universal quantum Turing machine
D. Deutsch · 1985
Earlier work this paper cites.
Quantum mechanical computers
R. Feynman · 1985
Earlier work this paper cites.
Probabilistic Boolean decision trees and the complexity of evaluating game trees
M. Saks and A. Wigderson · 1986
Earlier work this paper cites.
Forbidden intersections
P. Frankl and V. Rödl · 1987
Earlier work this paper cites.
Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes
L. Babai and S. Moran · 1988
Earlier work this paper cites.
Learnability and the Vapnik-Chervonenkis dimension
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth · 1989
Earlier work this paper cites.
Quantum computational networks
D. Deutsch · 1989
Earlier work this paper cites.
Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity
J. van Leeuwen, editor · 1990
Earlier work this paper cites.
Private vs. common random bits in communication complexity
I. Newman · 1991
Earlier work this paper cites.
Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states
C. Bennett and S. Wiesner · 1992
Earlier work this paper cites.
Rapid solution of problems by quantum computation
D. Deutsch and R. Jozsa · 1992
Earlier work this paper cites.
A rigorous time bound for factoring integers
H. W. Lenstra, Jr. and C. Pomerance · 1992
Earlier work this paper cites.
Algebraic methods for interactive proof systems
C. Lund, L. Fortnow, H. Karloff, and N. Nisan · 1992
Earlier work this paper cites.
IP = PSPACE
A. Shamir · 1992
Earlier work this paper cites.
IP = PSPACE: Simplified proof
A. Shen · 1992
Earlier work this paper cites.
Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
C. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. Wootters · 1993
Earlier work this paper cites.
The Development of the Number Field Sieve
A. K. Lenstra and H. W. Lenstra, Jr · 1993
Earlier work this paper cites.
Quantum circuit complexity
A. C-C. Yao · 1993
Earlier work this paper cites.
An approximate Fourier transform useful in quantum factoring
D. Coppersmith · 1994
Earlier work this paper cites.
Computational Complexity
C. H. Papadimitriou · 1994
Earlier work this paper cites.
Quantum measurements and the Abelian stabilizer problem
A. Yu. Kitaev · 1995
Earlier work this paper cites.
Scheme for reducing decoherence in quantum memory
P. W. Shor · 1995
Earlier work this paper cites.
Communication complexity in a 3-computer model
A. Ambainis · 1996
Earlier work this paper cites.
A quantum algorithm for finding the minimum
C. Dürr and P. Høyer · 1996
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. K. Grover · 1996
Earlier work this paper cites.
Threshold accuracy for quantum computation
M. Knill, R. Laflamme, and W. Zurek · 1996
Earlier work this paper cites.
Universal quantum simulators
S. Lloyd · 1996
Earlier work this paper cites.
Public vs. private coin flips in one round communication games
I. Newman and M. Szegedy · 1996
Earlier work this paper cites.
Multiple particle interference and quantum error correction
A. Steane · 1996
Earlier work this paper cites.
Stabilization of quantum computations by symmetrization
A. Barenco, A. Berthiaume, D. Deutsch, A. Ekert, R. Jozsa, and C. Macchiavello · 1997
Earlier work this paper cites.
Quantum computation of Fourier transforms over symmetric groups
R. Beals · 1997
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani · 1997
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1997
Earlier work this paper cites.
Quantum algorithm for the collision problem
G. Brassard, P. Høyer, and A. Tapp · 1997
Earlier work this paper cites.
Substituting quantum entanglement for communication
R. Cleve and H. Buhrman · 1997
Earlier work this paper cites.
P = BPP if E requires exponential circuits: Derandomizing the XOR lemma
R. Impagliazzo and A. Wigderson · 1997
Earlier work this paper cites.
The Art of Computer Programming. Volume 2: Seminumerical Algorithms
D. E. Knuth · 1997
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. W. Shor · 1997
Earlier work this paper cites.
Lower bounds for discrete logarithms and related problems
V. Shoup · 1997
Earlier work this paper cites.
On the power of quantum computation
D. Simon · 1997
Earlier work this paper cites.
Tight bounds on quantum searching
M. Boyer, G. Brassard, P. Høyer, and A. Tapp · 1998
Earlier work this paper cites.
Quantum vs. classical communication and computation
H. Buhrman, R. Cleve, and A. Wigderson · 1998
Earlier work this paper cites.
Quantum entanglement and the communication complexity of the inner product function
R. Cleve, W. van Dam, M. Nielsen, and A. Tapp · 1998
Earlier work this paper cites.
Quantum algorithms revisited
R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca · 1998
Earlier work this paper cites.
Quantum oracle interrogation: Getting all information for almost half the price
W. van Dam · 1998
Earlier work this paper cites.
Unconditional security in quantum cryptography
D. Mayers · 1998
Earlier work this paper cites.
The hidden subgroup problem and eigenvalue estimation on a quantum computer
M. Mosca and A. Ekert · 1998
Earlier work this paper cites.
Fault-tolerant quantum computation
J. Preskill · 1998
Earlier work this paper cites.
The cost of exactly simulating quantum entanglement with classical communication
G. Brassard, R. Cleve, and A. Tapp · 1999
Earlier work this paper cites.
Learning DNF over the uniform distribution using a quantum example oracle
N. H. Bshouty and J. C. Jackson · 1999
Earlier work this paper cites.
Complexity limitations on quantum computation
L. Fortnow and J. Rogers · 1999
Earlier work this paper cites.
Quantum NP, January 1999
A. Yu. Kitaev · 1999
Earlier work this paper cites.
Unconditional security of quantum key distribution over arbitrarily long distances
H-K. Lo and H. F. Chau · 1999
Earlier work this paper cites.
Classical computing, quantum computing, and Shor’s factoring algorithm
Y. Manin · 1999
Earlier work this paper cites.
Optimal lower bounds for quantum automata and random access codes
A. Nayak · 1999
Earlier work this paper cites.
A probabilistic algorithm for k k -SAT and constraint satisfaction problems
U. Schöning · 1999
Earlier work this paper cites.
Private quantum channels
A. Ambainis, M. Mosca, A. Tapp, and R. de Wolf · 2000
Earlier work this paper cites.
The query complexity of order-finding
R. Cleve · 2000
Cited alongside, same era.
An improved quantum Fourier transform algorithm and applications
L. Hales and S. Hallgren · 2000
Cited alongside, same era.
Quantum Fourier Sampling, the Hidden Subgroup Problem, and Beyond
S. J. Hallgren · 2000
Cited alongside, same era.
On the efficiency of local decoding procedures for error-correcting codes
J. Katz and L. Trevisan · 2000
Cited alongside, same era.
Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
A. Kitaev and J. Watrous · 2000
Cited alongside, same era.
Quantum Computation and Quantum Information
M. A. Nielsen and I. L. Chuang · 2000
Cited alongside, same era.
Variational quantum algorithms
M. Cerezo, A. Arrasmith, R. Babbush, S. Benjamin, S. Endo, K. Fujii, J. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. Coles · 2012
Later among the works it cites.
An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
G. Ivanyos, L. Sanselme, and M. Santha · 2012
Later among the works it cites.
Span-program-based quantum algorithm for evaluating formulas
B. Reichardt and R. Špalek · 2012
Later among the works it cites.
Guest column: The quantum PCP conjecture
D. Aharonov, I. Arad, and T. Vidick · 2013
Later among the works it cites.
Dual lower bounds for approximate degree and Markov-Bernstein inequalities
M. Bun and J. Thaler · 2013
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Quantum computing via measurements only, 2000
R. Raussendorf and H. J. Briegel · 2000
Cited alongside, same era.
Experimental realization of an order-finding algorithm with an NMR quantum computer
L. Vandersypen, M. Steffen, G. Breyta, C. Yannoni, R. Cleve, and I. Chuang · 2000
Cited alongside, same era.
Succinct quantum proofs for properties of finite groups
J. Watrous · 2000
Cited alongside, same era.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 2001
Cited alongside, same era.
Quantum fingerprinting
H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf · 2001
Cited alongside, same era.
Some optimal inapproximability results
J. Håstad · 2001
Cited alongside, same era.
Later among the works it cites.
Nested quantum walks with quantum data structures
S. Jeffery, R. Kothari, and F. Magniez · 2013
Later among the works it cites.
Quantum algorithms for supervised and unsupervised machine learning, 1 Jul 2013
S. Lloyd, M. Mohseni, and P. Rebentrost · 2013
Later among the works it cites.
Quantum principal component analysis
S. Lloyd, M. Mohseni, and P. Rebentrost · 2013
Later among the works it cites.
Approximating the AND-OR tree
A. Sherstov · 2013
Later among the works it cites.
Applications of the Adversary Method in Quantum Query Algorithms
A. Belovs · 2014
Later among the works it cites.
Exponential improvement in precision for simulating sparse Hamiltonians
D. Berry, A. Childs, R. Cleve, R. Kothari, and R. Somma · 2014
Later among the works it cites.
A. Bookatz · 2014
Later among the works it cites.
A quantum approximate optimization algorithm
E. Farhi, J. Goldstone, and S. Gutmann · 2014
Later among the works it cites.
Improved quantum algorithm for triangle finding via combinatorial arguments
F. Le Gall · 2014
Later among the works it cites.
A variational eigenvalue solver on a photonic quantum processor
A. Peruzzo, J. McClean, P. Shadbolt, M-H. Yung, X-Q. Zhou, P. Love, A. Aspuru-Guzik, and J. O’Brien · 2014
Later among the works it cites.
Quantum support vector machine for big data classification
P. Rebentrost, M. Mohseni, and S. Lloyd · 2014
Later among the works it cites.
Span programs are equivalent to quantum query algorithms
B. Reichardt · 2014
Later among the works it cites.
Understanding machine learning: From theory to algorithms
S. Shalev-Shwartz and S. Ben-David · 2014
Later among the works it cites.
Quantum machine learning algorithms: Read the fine print
S. Aaronson · 2015
Later among the works it cites.
Quantum algorithms for learning symmetric juntas via adversary bound
A. Belovs · 2015
Later among the works it cites.
Variations on quantum adversary, 27 Apr 2015
A. Belovs · 2015
Later among the works it cites.
Simulating Hamiltonian dynamics with a truncated Taylor series
D. Berry, A. Childs, R. Cleve, R. Kothari, and R. Somma · 2015
Later among the works it cites.
Hamiltonian simulation with nearly optimal dependence on all parameters
D. Berry, A. Childs, and R. Kothari · 2015
Later among the works it cites.
The Bose-Hubbard model is QMA-complete
A. M. Childs, D. Gosset, and Z. Webb · 2015
Later among the works it cites.
Quantum hamiltonian complexity
S. Gharibian, Y. Huang, Z. Landau, and S. W. Shin · 2015
Later among the works it cites.
Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres
B. Hensen, H. Bernien, A. E. Dréau, A. Reiserer, N. Kalb, M. S. Blok, J. Ruitenberg, R. F. L. Vermeulen, R. N. Schouten, C. Abellán, W. Amaya, V. Pruneri, M. W. Mitchell, M. Markham, D. J. Twitchen, D. Elkouss, S. Wehner, T. H. Taminiau, and R. Hanson · 2015
Later among the works it cites.
Quantum error correction for quantum memories
B. M. Terhal · 2015
Later among the works it cites.
Quantum proofs
T. Vidick and J. Watrous · 2015
Later among the works it cites.
Efficient quantum algorithms for (gapped) group testing and junta testing
A. Ambainis, A. Belovs, O. Regev, and R. de Wolf · 2016
Later among the works it cites.
Graph isomorphism in quasipolynomial time
L. Babai · 2016
Later among the works it cites.
Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
J-F. Biasse and F. Song · 2016
Later among the works it cites.
Improved classical simulation of quantum circuits dominated by Clifford gates
S. Bravyi and D. Gosset · 2016
Later among the works it cites.
Quantum cryptography beyond quantum key distribution
A. Broadbent and C. Schaffner · 2016
Later among the works it cites.
Sample-optimal tomography of quantum states
J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yi · 2016
Later among the works it cites.
The optimal sample complexity of PAC learning
S. Hanneke · 2016
Later among the works it cites.
Breaking symmetric cryptosystems using quantum period finding
M. Kaplan, G. Leurent, A. Leverrier, and M. Naya-Plasencia · 2016
Later among the works it cites.
Hamiltonian simulation by qubitization
G. H. Low and I. L. Chuang · 2016
Later among the works it cites.
Methodology of resonant equiangular composite quantum gates
G. H. Low, T. J. Yoder, and I. L. Chuang · 2016
Later among the works it cites.
R. O’Donnell and J. Wright · 2016
Later among the works it cites.
Guest column: A survey of quantum learning theory
S. Arunachalam and R. de Wolf · 2017
Later among the works it cites.
Optimizing the number of gates in quantum search
S. Arunachalam and R. de Wolf · 2017
Later among the works it cites.
Post-quantum cryptography
D. Bernstein and T. Lange · 2017
Later among the works it cites.
J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd · 2017
Later among the works it cites.
Quantum speed-ups for solving semidefinite programs
F. Brandão and K. Svore · 2017
Later among the works it cites.
Lecture notes on quantum algorithms, 2017
A. Childs · 2017
Later among the works it cites.
A. Childs, R. Kothari, and R. Somma · 2017
Later among the works it cites.
Advances in quantum reinforcement learning
V. Dunjko, J. Taylor, and H. Briegel · 2017
Later among the works it cites.
Quantum recommendation systems
I. Kerenidis and A. Prakash · 2017
Later among the works it cites.
Hamiltonian simulation with optimal sample complexity
S. Kimmel, G. H. Low C. Lin, M. Ozols, and T. Yoder · 2017
Later among the works it cites.
Improved quantum query algorithms for triangle finding and associativity testing
T. Lee, F. Magniez, and M. Santha · 2017
Later among the works it cites.
Hamiltonian simulation by uniform spectral amplification
G. H. Low and I. L. Chuang · 2017
Later among the works it cites.
Optimal Hamiltonian simulation by quantum signal processing
G. H. Low and I. L. Chuang · 2017
Later among the works it cites.
Using Simon’s algorithm to attack symmetric-key cryptographic primitives
T. Santoli and C. Schaffner · 2017
Later among the works it cites.
Optimal quantum sample complexity of learning algorithms
S. Arunachalam and R. de Wolf · 2018
Later among the works it cites.
Quantum gradient estimation and its application to quantum reinforcement learning
A. Cornelissen · 2018
Later among the works it cites.
Constant overhead quantum fault-tolerance with quantum expander codes
O. Fawzi, A. Grospellier, and A. Leverrier · 2018
Later among the works it cites.
Classical verification of quantum computations
U. Mahadev · 2018
Later among the works it cites.
Foundations of Machine Learning
M. Mohri, A. Rostamizadeh, and A. Talwalkar · 2018
Later among the works it cites.
The Theory of Quantum Information
J. Watrous · 2018
Later among the works it cites.
Quantum speedups for exponential-time dynamic programming algorithms
A. Ambainis, K. Balodis, J. Iraids, M. Kokainis, K. Prūsis, and J. Vihrovs · 2019
Closest in time.
Quantum algorithms for zero-sum games
J. van Apeldoorn and A. Gilyén · 2019
Closest in time.
Improvements in quantum SDP-solving with applications
J. van Apeldoorn and A. Gilyén · 2019
Closest in time.
Quantum query algorithms are completely bounded forms
S. Arunachalam, J. Briët, and C. Palazuelos · 2019
Closest in time.
Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning
F. Brandão, A. Kalev, T. Li, C. Lin, K. Svore, and X. Wu · 2019
Closest in time.
Quantum chemistry in the age of quantum computing
Y. Cao, J. Romero, J. Olson, M. Degroote, P. Johnson, M. Kieferová, I. Kivlichan, T. Menke, B. Peropadre, N. Sawaya, S. Sim, L. Veis, and A. Aspuru-Guzik · 2019
Closest in time.
S. Chakraborty, A. Gilyén, and S. Jeffery · 2019
Closest in time.
A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu · 2019
Closest in time.
Quantum Singular Value Transformation & Its Algorithmic Applications
A. Gilyén · 2019
Closest in time.
Optimizing quantum optimization algorithms via faster quantum gradient computation
A. Gilyén, S. Arunachalam, and N. Wiebe · 2019
Closest in time.
A. Gilyén, Y. Su, G. H. Low, and N. Wiebe · 2019
Closest in time.
Integer multiplication in time O ( n log n ) O(n\log n)
D. Harvey and J. van der Hoeven · 2019
Closest in time.
q-means: A quantum algorithm for unsupervised machine learning
I. Kerenidis, J. Landman, A. Luongo, and A. Prakash · 2019
Closest in time.
Optimal quantum eigenstate filtering with application to solving quantum linear systems
L. Lin and Y. Tong · 2019
Closest in time.
Quantum machine learning in feature Hilbert spaces
M. Schuld and N. Killoran · 2019
Closest in time.
A quantum-inspired classical algorithm for recommendation systems
E. Tang · 2019
Closest in time.
Quantum SDP-solvers: better upper and lower bounds
J. van Apeldoorn, A. Gilyén, S. Gribling, and R. de Wolf · 2020
Closest in time.
The quantum query complexity of composition with a relation
A. Belovs and T. Lee · 2020
Closest in time.
Improved upper bounds on the stabilizer rank of magic states
H. Qassim, H. Pashayan, and D. Gosset · 2021
Closest in time.
Quantum semi-supervised kernel learning
S. Saeedi, A. Panahi, and T. Arodz · 2021
Closest in time.
Machine Learning with Quantum Computers
M. Schuld and F. Petruccione · 2021
Closest in time.
Learning quantum circuits of some T T gates
C-Y. Lai and H-C. Cheng · 2022
Closest in time.
Lecture notes on quantum algorithms for scientific computation, 2022
L. Lin · 2022
Closest in time.
Quantum computing 40 years later
J. Preskill · 2022
Closest in time.
A near-cubic lower bound for 3-query locally decodable codes from semirandom csp refutation
O. Alrabiah, V. Guruswami, P. Kothari, and P. Manohar · 2023
Closest in time.
Quantum algorithms and lower bounds for linear regression with norm constraints
Y. Chen and R. de Wolf · 2023
Closest in time.
A quantum speed-up for approximating the top eigenvectors of a matrix
Y. Chen, A. Gilyén, and R. de Wolf · 2024
Closest in time.
An exponential lower bound for linear 3-query locally correctable codes
P. Kothari and P. Manohar · 2024
Closest in time.
Quantum error correction below the surface code threshold
Google Quantum AI and Collaborators · 2025
Closest in time.