Fetching the paper…
Reading the bibliography…
Achieving superpolynomial speedups for optimization has long been a central goal for quantum algorithms.
Low-density parity-check codes
Robert Gallager · 1962
Earlier work this paper cites.
The use of information sets in decoding cyclic codes
Eugene Prange · 1962
Earlier work this paper cites.
Low-Density Parity-Check Codes
Robert G. Gallager · 1963
Earlier work this paper cites.
New generalizations of the Reed-Muller codes–I: Primitive codes
Tadao Kasami, Shu Lin, and W. Peterson · 1968
Earlier work this paper cites.
On generalized Reed-Muller codes and their relatives
Philippe Delsarte, Jean-Marie Goethals, and F. J. MacWilliams · 1970
Earlier work this paper cites.
Matching, Euler tours and the Chinese postman
Jack Edmonds and Ellis L. Johnson · 1973
Earlier work this paper cites.
On the inherent intractability of certain coding problems
Elwyn Berlekamp, Robert McEliece, and Henk Van Tilborg · 1978
Earlier work this paper cites.
Factoring polynomials with rational coefficients
Arjen K. Lenstra, Hendrik Willem Lenstra, and László Lovász · 1982
Earlier work this paper cites.
A hierarchy of polynomial time lattice basis reduction algorithms
Claus-Peter Schnorr · 1987
Earlier work this paper cites.
Approximate counting, uniform generation and rapidly mixing Markov chains
Alistair Sinclair and Mark Jerrum · 1989
Earlier work this paper cites.
The role of relativization in complexity theory
Lance Fortnow · 1994
Earlier work this paper cites.
Lattice basis reduction: Improved practical algorithms and solving subset sum problems
Claus-Peter Schnorr and Martin Euchner · 1994
Earlier work this paper cites.
On the error-correcting capabilities of cycle codes of graphs
Laurent Decreusefond and Gilles Zémor · 1997
Earlier work this paper cites.
Improved decoding of Reed-Solomon and algebraic-geometric codes
Venkatesan Guruswami and Madhu Sudan · 1998
Earlier work this paper cites.
Oblivious transfer and polynomial evaluation
Moni Naor and Benny Pinkas · 1999
Earlier work this paper cites.
Noisy polynomial interpolation and noisy Chinese remaindering
Daniel Bleichenbacher and Phong Q. Nguyen · 2000
Earlier work this paper cites.
On bounded occurrence constraint satisfaction
Johan Håstad · 2000
Earlier work this paper cites.
A sieve algorithm for the shortest lattice vector problem
Miklós Ajtai, Ravi Kumar, and Dandapani Sivakumar · 2001
Earlier work this paper cites.
A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda · 2001
Earlier work this paper cites.
The capacity of low-density parity-check codes under message-passing decoding
Thomas J. Richardson and Rüdiger L. Urbanke · 2001
Earlier work this paper cites.
Design of capacity-approaching irregular low-density parity-check codes
Thomas J. Richardson, Mohammad Amin Shokrollahi, and Rüdiger L. Urbanke · 2001
Earlier work this paper cites.
Improved quantum circuits for elliptic curve discrete logarithms
Thomas Häner, Samuel Jaques, Michael Naehrig, Martin Roetteler, and Mathias Soeken · 2001
Earlier work this paper cites.
Adiabatic quantum state generation and statistical zero knowledge
Dorit Aharonov and Amnon Ta-Shma · 2003
Earlier work this paper cites.
Quantum computation and lattice problems
Oded Regev · 2004
Earlier work this paper cites.
List decoding of q q -ary Reed-Muller codes
Ruud Pellikaan and Xin-Wen Wu · 2004
Earlier work this paper cites.
Noisy interpolation of sparse polynomials in finite fields
Igor Shparlinski and Arne Winterhof · 2005
Earlier work this paper cites.
Playing “hide-and-seek” with numbers
Igor E. Shparlinski · 2005
Earlier work this paper cites.
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard
Venkatesan Guruswami and Alexander Vardy · 2005
Earlier work this paper cites.
Lattice problems in NP ∩ \cap coNP
Dorit Aharonov and Oded Regev · 2005
Earlier work this paper cites.
Using linear programming to decode binary linear codes
Jon Feldman, Martin J. Wainwright, and David R. Karger · 2005
Earlier work this paper cites.
Oblivious polynomial evaluation
Moni Naor and Benny Pinkas · 2006
Earlier work this paper cites.
Spectral approach to linear programming bounds on codes
Alexander M. Barg and Dmitry Yu. Nogin · 2006
Cited alongside, same era.
On the list and bounded distance decodability of Reed-Solomon codes
Qi Cheng and Daqing Wan · 2007
Cited alongside, same era.
LP decoding corrects a constant fraction of errors
Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein, and Martin J. Wainwright · 2007
Cited alongside, same era.
Complexity of decoding positive-rate Reed-Solomon codes
Qi Cheng and Daqing Wan · 2008
Cited alongside, same era.
Probabilistic analysis of linear programming decoding
Constantinos Daskalakis, Alexandros G. Dimakis, Richard M. Karp, and Martin J. Wainwright · 2008
Cited alongside, same era.
Adaptive methods for linear programming decoding
Mohammad H. Taghavi and Paul H. Siegel · 2008
Cited alongside, same era.
The quantum approximate optimization algorithm at high depth for MaxCut on large-girth regular graphs and the Sherrington-Kirkpatrick model
Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou · 2022
Later among the works it cites.
Quantum algorithms for variants of average-case lattice problems via filtering
Yilei Chen, Qipeng Liu, and Mark Zhandry · 2022
Later among the works it cites.
Quantum advantage for combinatorial optimization problems, simplified
Mario Szegedy · 2022
Later among the works it cites.
An efficient quantum algorithm for lattice problems achieving subexponential approximation factor
Lior Eldar and Sean Hallgren · 2022
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Fuzzy extractors: How to generate strong keys from biometrics and other noisy data
Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith · 2008
Cited alongside, same era.
Information, Physics, and Computation
Mark Mézard and Andrea Montanari · 2009
Cited alongside, same era.
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · 2009
Cited alongside, same era.
Valid inequalities for binary linear codes
Akin Tanatmis, Stefan Ruzika, Horst W. Hamacher, Mayur Punekar, Frank Kienle, and Norbert Wehn · 2009
Cited alongside, same era.
The exponential complexity of satisfiability problems
Chris Calabro · 2009
Cited alongside, same era.
Quantum Computation and Quantum Information
Michael A. Nielsen and Isaac L. Chuang · 2010
Cited alongside, same era.
Andreas Bartschi and Stephan Eidenbenz · 2022
Later among the works it cites.
Verifiable quantum advantage without structure
Takashi Yamakawa and Mark Zhandry · 2022
Later among the works it cites.
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
Nai-Hui Chia, András Pal Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang · 2022
Later among the works it cites.
Quantum message-passing algorithm for optimal and efficient decoding
Christophe Piveteau and Joseph M. Renes · 2022
Later among the works it cites.
Bounds on approximating Max- k k -XOR with quantum and classical local algorithms
Kunal Marwaha and Stuart Hadfield · 2022
Later among the works it cites.
Performance of the QAOA on MaxCut over large-girth regular graphs
Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, and Leo Zhou · 2022
Later among the works it cites.
Mind the gap: achieving a super-Grover quantum speedup by jumping to the end
Alexander M. Dalzell, Nicola Pancotti, Earl T. Campbell, and Fernando G.S.L. Brandão · 2023
Later among the works it cites.
On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms
Eliot Kapit, Brandon A. Barton, Sean Feeney, George Grattan, Pratik Patnaik, Jacob Sagal, Lincoln D. Carr, and Vadim Oganesyan · 2023
Later among the works it cites.
A quantum-classical performance separation in nonconvex optimization
Jiaqi Leng, Yufan Zheng, and Xiaodi Wu · 2023
Later among the works it cites.
Quantum reduction of finding short code vectors to the decoding problem
Thomas Debris-Alazard, Maxime Remaud, and Jean-Pierre Tillich · 2023
Later among the works it cites.
Essential Coding Theory
Venkatesan Guruswami, Atri Rudra, and Madhu Sudan · 2023
Later among the works it cites.
How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates
Daniel Litinski · 2023
Later among the works it cites.
Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem
R. Shaydulin, C. Li, S. Chakrabarti, M. DeCross, D. Herman, N. Kumar, J. Larson, D. Lykov, P. Minssen, Y. Sun, Y. Alexeev, J. M. Dreiling, J. P. Gaebler, T. M. Gatterman, J. A. Gerber, K. Gilmore, D. Gresh, N. Hewitt, C. V. Horst, S. Hu, J. Johansen, M. Matheny, T. Mengle, M. Mills, S. A. Moses, B. Neyenhuis, P. Siegfried, R. Yalovetzky, and M. Pistoia · 2024
Closest in time.
An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory
Niklas Pirnay, Vincent Ulitzsh, Frederik Wilde, Jens Eisert, and Jean-Pierre Seifert · 2024
Closest in time.
Quantum state preparation using an exact CNOT synthesis formulation
Hanyu Wang, Bochen Tan, Jason Cong, and Giovanni De Micheli · 2024
Closest in time.
Expressing and analyzing quantum algorithms with qualtran
Matthew P. Harrigan, Tanuj Khattar, Charles Yuan, Anurudh Peduri, Noureldin Yosri, Fionn D. Malone, Ryan Babbush, and Nicholas C. Rubin · 2024
Closest in time.
André Chailloux and Jean-Pierre Tillich · 2024
Closest in time.
Quantum advantage from soft decoders
André Chailloux and Jean-Pierre Tillich · 2024
Closest in time.
Trading T-gates for dirty qubits in state preparation and unitary synthesis
Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer · 2024
Closest in time.
Reducing the number of qubits in quantum information set decoding
Clémence Chevignard, Pierre-Alain Fouque, and André Schrottenloher · 2024
Closest in time.
Measurement-based uncomputation of quantum circuits for modular arithmetic
Alessandro Luongo, Antonio Michele Miti, Varun Narasimhachar, and Adithya Sireesh · 2024
Closest in time.
Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA
Edward Farhi, Sam Gutmann, Daniel Ranard, and Benjamin Villalonga · 2025
Closest in time.
Quartic quantum speedups for planted inference
Alexander Schmidhuber, Ryan O’Donnell, Robin Kothari, and Ryan Babbush · 2025
Closest in time.
Quantum circuit design for decoded quantum interferometry
Natchapol Patamawisut, Naphan Benchasattabuse, Michal Hajdušek, and Rodney Van Meter · 2025
Closest in time.
Sami Boulebnane, Abid Khan, Minzhao Liu, Jeffrey Larson, Dylan Herman, Ruslan Shaydulin, and Marco Pistoia · 2025
Closest in time.
New circuit for quantum adder by constant
Dmytro Fedoriaka · 2025
Closest in time.