Fetching the paper…
Reading the bibliography…
We show the following hold, unconditionally unless otherwise stated, relative to a random oracle: - There are NP search problems solvable by quantum polynomial-time machines but not classical probabilistic polynomial-time machines.
A subexponential algorithm for the discrete logarithm problem with applications to cryptography
Leonard Adleman · 1979
Earlier work this paper cites.
Tricks or treats with the hilbert matrix
Man-Duen Choi · 1983
Earlier work this paper cites.
Limits on the provable consequences of one-way permutations
Russell Impagliazzo and Steven Rudich · 1989
Earlier work this paper cites.
Random oracles are practical: A paradigm for designing efficient protocols
Mihir Bellare and Phillip Rogaway · 1993
Earlier work this paper cites.
Quantum complexity theory
Ethan Bernstein and Umesh V. Vazirani · 1993
Earlier work this paper cites.
Algorithms for quantum computation: Discrete logarithms and factoring
Peter W. Shor · 1994
Earlier work this paper cites.
A personal view of average-case complexity
R. Impagliazzo · 1995
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh V. Vazirani · 1997
Earlier work this paper cites.
Finite fields
Rudolf Lidl and Harald Niederreiter · 1997
Earlier work this paper cites.
On the power of quantum computation
Daniel R. Simon · 1997
Earlier work this paper cites.
Quantum lower bounds by polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf · 1998
Earlier work this paper cites.
The random oracle methodology, revisited (preliminary version)
Ran Canetti, Oded Goldreich, and Shai Halevi · 1998
Earlier work this paper cites.
Improved decoding of reed-solomon and algebraic-geometry codes
Venkatesan Guruswami and Madhu Sudan · 1999
Earlier work this paper cites.
A pseudorandom generator from any one-way function
Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby · 1999
Earlier work this paper cites.
Quantum lower bounds by polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf · 2001
Earlier work this paper cites.
Complexity measures and decision tree complexity: a survey
Harry Buhrman and Ronald de Wolf · 2002
Earlier work this paper cites.
Sharp quantum versus classical query complexity separations
J. Niel de Beaudrap, Richard Cleve, and John Watrous · 2002
Earlier work this paper cites.
Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem
Sean Hallgren · 2002
Earlier work this paper cites.
Exponential algorithmic speedup by a quantum walk
Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman · 2003
Earlier work this paper cites.
Reed-solomon codes for correcting phased error bursts
Victor Yu. Krachkovsky · 2003
Earlier work this paper cites.
Quantum lower bounds for the collision and the element distinctness problems
Scott Aaronson and Yaoyun Shi · 2004
Earlier work this paper cites.
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · 2005
Earlier work this paper cites.
A Public Key Cryptosystem Based On Pell Equation
Sahadeo Padhye · 2006
Earlier work this paper cites.
Quantum algorithms for some hidden shift problems
Wim van Dam, Sean Hallgren, and Lawrence Ip · 2006
Cited alongside, same era.
List Decoding and Property Testing of Error Correcting Codes
Atri Rudra · 2007
Cited alongside, same era.
Random oracles and auxiliary input
Dominique Unruh · 2007
Cited alongside, same era.
Explicit codes achieving list decoding capacity: Error-correction with optimal redundancy
Venkatesan Guruswami and Atri Rudra · 2008
Cited alongside, same era.
Why simple hash functions work: exploiting the entropy in a data stream
Michael Mitzenmacher and Salil P. Vadhan · 2008
Cited alongside, same era.
Polynomial-time theory of matrix groups
László Babai, Robert Beals, and Ákos Seress · 2009
Cited alongside, same era.
Succinct arguments in the quantum random oracle model
Alessandro Chiesa, Peter Manohar, and Nicholas Spooner · 2019
Later among the works it cites.
Security of the Fiat-Shamir transformation in the quantum random-oracle model
Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner · 2019
Later among the works it cites.
Quantum random oracle model with auxiliary input
Minki Hhan, Keita Xagawa, and Takashi Yamakawa · 2019
Later among the works it cites.
Revisiting post-quantum Fiat-Shamir
Qipeng Liu and Mark Zhandry · 2019
Later among the works it cites.
One-shot signatures and applications to hybrid quantum/classical authentication
Ryan Amos, Marios Georgiou, Aggelos Kiayias, and Mark Zhandry · 2020
Later among the works it cites.
Simpler proofs of quantumness
Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani, and Thomas Vidick · 2020
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd · 2010
Cited alongside, same era.
The computational complexity of linear optics
Scott Aaronson and Alex Arkhipov · 2011
Cited alongside, same era.
Random oracles in a quantum world
Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry · 2011
Cited alongside, same era.
Secure identity-based encryption in the quantum random oracle model
Mark Zhandry · 2012
Cited alongside, same era.
The need for structure in quantum speedups
Scott Aaronson and Andris Ambainis · 2014
Cited alongside, same era.
Quantum attacks on classical proof systems: The hardness of quantum rewinding
Andris Ambainis, Ansis Rosmanis, and Dominique Unruh · 2014
Cited alongside, same era.
Classical verification of quantum computations with efficient verifier
Nai-Hui Chia, Kai-Min Chung, and Takashi Yamakawa · 2020
Later among the works it cites.
Tight quantum time-space tradeoffs for function inversion
Kai-Min Chung, Siyao Guo, Qipeng Liu, and Luowen Qian · 2020
Later among the works it cites.
Fiat-Shamir via list-recoverable codes (or: parallel repetition of GMW is not zero-knowledge)
Justin Holmgren, Alex Lombardi, and Ron D. Rothblum · 2021
Later among the works it cites.
Classical vs quantum random oracles
Takashi Yamakawa and Mark Zhandry · 2021
Later among the works it cites.
On the impossibility of key agreements from quantum random oracles
Per Austrin, Hao Chung, Kai-Min Chung, Shiuan Fu, Yao-Ting Lin, and Mohammad Mahmoody · 2022
Closest in time.
Quantum depth in the random oracle model
Atul Singh Arora, Andrea Coladangelo, Matthew Coudron, Alexandru Gheorghiu, Uttam Singh, and Hendrik Waldner · 2023
Closest in time.
Quantum advantage from any non-local game
Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang · 2023
Closest in time.
Introduction to coding theory lecture notes, 2010
Yehuda Lindell · 2023
Closest in time.
Non-uniformity and quantum advice in the quantum random oracle model
Qipeng Liu · 2023
Closest in time.
Proofs of quantumness from trapdoor permutations
Tomoyuki Morimae and Takashi Yamakawa · 2023
Closest in time.
Oracle separation of QMA and QCMA with bounded adaptivity
Shalev Ben-David and Srijita Kundu · 2024
Closest in time.
Quantum communication advantage in tfnp, 2024
Mika Göös, Tom Gur, Siddhartha Jain, and Jiawei Li · 2024
Closest in time.
On pigeonhole principles and ramsey in tfnp
Siddhartha Jain, Jiawei Li, Robert Robere, and Zhiyang Xun · 2024
Closest in time.
Optimization by decoded quantum interferometry, 2024
Stephen P. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei V. Isakov, and Ryan Babbush · 2024
Closest in time.
A quantum ”lifting theorem” for constructions of pseudorandom generators from random oracles, 2024
Jonathan Katz and Ben Sela · 2024
Closest in time.
Total NP search problems with abundant solutions
Jiawei Li · 2024
Closest in time.
Classical vs quantum advice and proofs under classically-accessible oracle
Xingjian Li, Qipeng Liu, Angelos Pelecanos, and Takashi Yamakawa · 2024
Closest in time.