Fetching the paper…
Reading the bibliography…
We study the complexity of Decoded Quantum Interferometry (DQI), a quantum algorithm for approximate optimization.
“Fine-grained quantum computational supremacy”
Tomoyuki Morimae and Suguru Tamaki · 1901
Earlier work this paper cites.
“Classical and quantum bounded depth approximation algorithms”, 2019
M.. Hastings · 1905
Earlier work this paper cites.
Naomi Kirshner and Alex Samorodnitsky · 1909
Earlier work this paper cites.
“Sur une généralisation des polynômes d’Hermite”
Mikhail Krawtchouk · 1929
Earlier work this paper cites.
“Orthogonal Polynomials”
G Szegő · 1939
Earlier work this paper cites.
“A theorem on the distribution of weights in a systematic code”
Jessie MacWilliams · 1963
Earlier work this paper cites.
“An algebraic approach to the association schemes of coding theory”
Philippe Delsarte · 1973
Earlier work this paper cites.
“A Krawtchouk polynomial addition theorem and wreath products of symmetric groups”
Charles Dunkl · 1976
Earlier work this paper cites.
“The theory of error-correcting codes”
Florence MacWilliams and Neil Sloane · 1977
Earlier work this paper cites.
“New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities”
Robert McEliece, Eugene Rodemich, Howard Rumsey and Lloyd Welch · 1977
Earlier work this paper cites.
“The complexity of approximate counting”
Larry Stockmeyer · 1983
Earlier work this paper cites.
“A hard-core predicate for all one-way functions”
Oded Goldreich and Leonid Levin · 1989
Earlier work this paper cites.
“Difference analogs of the harmonic oscillator”
Natig Atakishiev and Sergei Suslov · 1990
Earlier work this paper cites.
“Zeros of generalized Krawtchouk polynomials”
Laura Chihara and Dennis Stanton · 1990
Earlier work this paper cites.
“An upper bound on the covering radius as a function of the dual distance”
AA Tietavainen · 1990
Earlier work this paper cites.
“Learning decision trees using the Fourier spectrum”
Eyal Kushilevitz and Yishay Mansour · 1991
Earlier work this paper cites.
“Introduction to Coding Theory”, GTM Series
J.H. van Lint · 1992
Earlier work this paper cites.
“Algorithms for quantum computation: discrete logarithms and factoring”
Peter Shor · 1994
Earlier work this paper cites.
“Packing radius, covering radius, and dual distance”
Patrick Solé · 1995
Earlier work this paper cites.
“Quantum MacWilliams Identities”, 1996
Peter Shor and Raymond Laflamme · 1996
Earlier work this paper cites.
“Fractional fourier–kravchuk transform”
Natig Atakishiyev and Kurt Wolf · 1997
Earlier work this paper cites.
“Strong asymptotics for Krawtchouk polynomials”
Mourad Ismail and Plamen Simeonov · 1998
Earlier work this paper cites.
“Continuous vs. discrete fractional Fourier transforms”
Natig Atakishiyev, Luis Vicent and Kurt Wolf · 1999
Earlier work this paper cites.
“The canonical Kravchuk basis for discrete quantummechanics”
Tugrul Hakioglu and Kurt Wolf · 2000
Earlier work this paper cites.
“Encoding a qubit in an oscillator”
Daniel Gottesman, Alexei Kitaev and John Preskill · 2001
Earlier work this paper cites.
“Quantum computing and quadratically signed weight enumerators”
E. Knill and R. Laflamme · 2001
Earlier work this paper cites.
“Association schemes and coding theory”
Philippe Delsarte and Vladimir. Levenshtein · 2002
Earlier work this paper cites.
“Efficient quantum algorithms for estimating gauss sums”, 2002
Wim Van and Gadiel Seroussi · 2002
Earlier work this paper cites.
“A Lattice Problem in Quantum NP”, 2003
Dorit Aharonov and Oded Regev · 2003
Earlier work this paper cites.
“Exponential algorithmic speedup by a quantum walk”
Andrew Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann and Daniel Spielman · 2003
Earlier work this paper cites.
“Hardness of approximating the weight enumerator of a binary linear code”, 2003
Michael. Vyalyi · 2003
Earlier work this paper cites.
“Generalized Alon–Boppana Theorems and Error-Correcting Codes”
Joel Friedman and Jean-Pierre Tillich · 2005
Earlier work this paper cites.
“Krawtchouk matrices from classical and quantum random walks”, 2007
Philip Feinsilver and Jerzy Kocik · 2007
Earlier work this paper cites.
“On the Exact Evaluation of Certain Instances of the Potts Partition Function by Quantum Computers”
Joseph Geraci and Daniel. Lidar · 2008
Cited alongside, same era.
“On bounded distance decoding, unique shortest vectors, and the minimum distance problem”
Vadim Lyubashevsky and Daniele Micciancio · 2009
Cited alongside, same era.
“Linear programming bounds for codes via a covering argument”
Michael Navon and Alex Samorodnitsky · 2009
Cited alongside, same era.
“Simulating quantum computers with probabilistic methods”, 2009
Maartenvanden Nest · 2009
Cited alongside, same era.
“Public-key cryptosystems from the worst-case shortest vector problem”
Chris Peikert · 2009
Cited alongside, same era.
“On lattices, learning with errors, random linear codes, and cryptography”
Matthew. Hastings · 2021
Later among the works it cites.
“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.
“Classically verifiable quantum advantage from a computational Bell test”
Gregory Kahanamoku-Meyer, Soonwon Choi, Umesh Vazirani and Norman Yao · 2022
Later among the works it cites.
“New LP-based upper bounds in the rate-vs.-distance problem for linear codes”, 2022
Elyassaf Loyfer and Nati Linial · 2022
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Oded Regev · 2009
Cited alongside, same era.
“The discrete Fourier transform and the quantum-mechanical oscillator in a finite-dimensional Hilbert space”
Thalanayar Santhanam and Balu Santhanam · 2009
Cited alongside, same era.
“Classical Ising model test for quantum circuits”
Joseph Geraci and Daniel Lidar · 2010
Cited alongside, same era.
“15-859V: Introduction to Coding Theory”
Venkatesan Guruswami · 2010
Cited alongside, same era.
“The computational complexity of linear optics”
Scott Aaronson and Alex Arkhipov · 2011
Cited alongside, same era.
Michael Bremner, Richard Jozsa and Dan Shepherd · 2011
Cited alongside, same era.
“On krawtchouk polynomials”, 2011
Rodney Coleman · 2011
Cited alongside, same era.
Later among the works it cites.
“Coding Theory” Lecture notes, 2023
Arpon Basu · 2023
Later among the works it cites.
“The complexity of the shortest vector problem”
Huck Bennett · 2023
Later among the works it cites.
“Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs”, 2023
Antares Chen, Neng Huang and Kunal Marwaha · 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.
“One more proof of the first linear programming bound for binary codes and two conjectures”
Alex Samorodnitsky · 2023
Later among the works it cites.
“Sum-of-squares hierarchies for binary polynomial optimization”
Lucas Slot and Monique Laurent · 2023
Later among the works it cites.
“New Solutions to Delsarte’s Dual Linear Programs”, 2024
André Chailloux and Thomas Debris-Alazard · 2024
Later among the works it cites.
“The Quantum Decoding Problem”
André Chailloux and Jean-Pierre Tillich · 2024
Later among the works it cites.
“Discrete quantum harmonic oscillator and Kravchuk transform”
Quentin Chauleur and Erwan Faou · 2024
Later among the works it cites.
“Weight distribution of random linear codes and Krawtchouk polynomials”
Alex Samorodnitsky · 2024
Later among the works it cites.
“Verifiable quantum advantage without structure”
Takashi Yamakawa and Mark Zhandry · 2024
Later among the works it cites.
“Decoded quantum interferometry requires structure”, 2025
Eric Anschuetz, David Gamarnik and Jonathan Lu · 2025
Closest in time.
“A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire”
John Bostanci, Barak Nehoran and Mark Zhandry · 2025
Closest in time.
“Decoded Quantum Interferometry Under Noise”, 2025
Kaifeng Bu, Weichen Gu, Dax Koh and Xiang Li · 2025
Closest in time.
“Continuous-Variable Quantum MacWilliams Identities”, 2025
Ansgar. Burchards · 2025
Closest in time.
“Quantum Advantage from Soft Decoders”
André Chailloux and Jean-Pierre Tillich · 2025
Closest in time.
“Lower bounding the MaxCut of high girth 3-regular graphs using the QAOA”, 2025
Edward Farhi, Sam Gutmann, Daniel Ranard and Benjamin Villalonga · 2025
Closest in time.
“Quantum Hermite Transform and Gaussian Goldreich-Levin”, 2025
Vishnu Iyer and Siddhartha Jain · 2025
Closest in time.
“Efficient Quantum Hermite Transform”, 2025
Siddhartha Jain, Vishnu Iyer, Rolando Somma, Ning Bao and Stephen Jordan · 2025
Closest in time.
“Optimization by Decoded Quantum Interferometry”, 2025
Stephen. Jordan, Noah Shutty, Mary Wootters, Adam Zalcman, Alexander Schmidhuber, Robbie King, Sergei. Isakov, Tanuj Khattar and Ryan Babbush · 2025
Closest in time.
“Verifiable quantum advantage via optimized DQI circuits”, 2025
Tanuj Khattar, Noah Shutty, Craig Gidney, Adam Zalcman, Noureldin Yosri, Dmitri Maslov, Ryan Babbush and Stephen Jordan · 2025
Closest in time.
“No exponential quantum speedup for SIS ∞ anymore”, 2025
Robin Kothari, Ryan O’Donnell and Kewen Wu · 2025
Closest in time.
“Quantum algorithms for representation-theoretic multiplicities”
Martin Larocca and Vojtech Havlicek · 2025
Closest in time.
“No quantum advantage in decoded quantum interferometry for maxcut”, 2025
Ojas Parekh · 2025
Closest in time.
“Hamiltonian decoded quantum interferometry”, 2025
Alexander Schmidhuber, Jonathan Lu, Noah Shutty, Stephen Jordan, Alexander Poremba and Yihui Quek · 2025
Closest in time.
“Quantum Advantage via Solving Multivariate Polynomials”
Pierre Briaud, Itai Dinur, Riddhi Ghosal, Aayush Jain, Paul Lou and Amit Sahai · 2026
Closest in time.
“Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry”, 2026
Maximilian. Kramer, Carsten Schubert and Jens Eisert · 2026
Closest in time.