Quantum Query Complexity Beyond the Worst Case

Amin Shiraz Gilani; Srinivasan Arunachalam; Yanlin Chen

REVIEW

Quantum Query Complexity Beyond the Worst Case

Srinivasan Arunachalam, Yanlin Chen, Amin Shiraz Gilani

Quantum Physics · Submitted 28 Sep 2026 · 127 references

Pith's verdict: A real research program is born here, but the factor of trust it earns rests on one hand-verified averaging lemma and one unverified reversible reduction; send it to a referee with both flagged as the explicit verification targets.

T0 · AI review

How this review was made: An AI referee (deepseek/deepseek-v4-flash) read the paper on September 29, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 4 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2609.35580 (version 1)

Pith IDHGF6ZU3D, Pith's permanent record of this paper and its review

CitationAmin Shiraz Gilani, Srinivasan Arunachalam, Yanlin Chen. "Quantum Query Complexity Beyond the Worst Case." arXiv:2609.35580 (2026). https://pith.science/paper/HGF6ZU3D

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

This paper initiates a real research program: smoothed quantum query complexity. That framing is genuinely absent from the cited literature, and the framework is clean and well-motivated. The headline results deserve the attention they are getting. The total-Simon separation (Theorem 3.2 plus Lemma 3.4) is the cleanest thing in the paper, and it holds up. I re-checked the full probability chain - Chernoff/McDiarmid on singleton fibers (Lemma 3.3), the union bound over nonzero a, and the fallback-to-truth-table trick - and it is all elementary and correct. The fallback makes the algorithm exact on every input while expected cost stays O(n/σ), and the classical lower bound rides legitimately on the published AW01 average-case bound. That is a solid standalone result. Theorem 4.1, the symmetric-function characterization, is the deepest and the place to be careful. The two-parameter framework (transcost and weighted influence) is well-motivated, and it degrades correctly at σ=0 to Beals et al. and at σ=1 to Ambainis-de Wolf - direct evidence it is not reverse-engineered to fit. But the averaging engine, Lemma 4.5, is an intricate interval-partition and anti-concentration argument, produced with GPT assistance and hand-verified only. The authors disclose this plainly in Section 1.2, which is to their credit, and a stress-test pass re-derived the main identities without finding an error. Still, a wrong constant in the |I|-regime split or a mode landing on an interval boundary would shift an eΘ factor, and with it the characterization. That is not a demonstrated flaw; it is an unverified, load-bearing step - exactly the kind of slip hand verification misses. It needs an independent check before the characterization is trusted. The string results are real: the collision-estimator improvement (ε^{-2/3} versus ε^{-25/24}) is concrete and checkable, and the Ulam and edit-distance bounds genuinely improve on [AN10] and [LGS22]. The soft spot there is the reversible implementation of the [AK12] reduction in Appendix A.5 - an original construction whose correctness depends on the locality and separation properties of [AK12] Lemma 4.6. The appendix is careful and conditions on the right event, but it has not been independently checked. The general-m cases asserted without proof in an otherwise tight pattern-matching bound are minor. This deserves a serious referee. The right verdict is conditional, not accept: send it out with Lemma 4.5 and Appendix A.5 as the explicit verification targets. I would bring it to the reading group.

Referee report

Significance

If the results hold, this is a substantial contribution to quantum query complexity. The framework is clean and genuinely interpolates worst- and average-case analyses; the endpoint consistency is checked (σ = 0 reproduces the Beals et al. characterization for symmetric functions, σ = 1 the Ambainis–de Wolf regime, Tables 1 and 2). The total-Simon separation is elementary and compelling, and the explicit-pattern smoothed pattern-matching bounds are proven with matching lower bounds, including a careful adversary argument. The quantum collision-estimation improvement over [GN22] is of independent interest, and the collision-enumeration adaptation of [BLSS25] to a fixed matching (Appendix A.4) is given as a self-contained proof with quantum-walk details, which is commendable for verifiability.

Major objections (3)

[§2.3 and §3 (Theorem 3.2 proof, paragraph before Lemma 3.3)] The perturbation model is defined in §2.3 by a bitwise rule (y_i = x_i with prob 1−σ, and 1/0 with prob σ/2), but the Simon proof analyzes a different model: each truth-table entry is resampled uniformly from F_2^n with probability σ. These are not equivalent: bitwise flips do not produce uniform resampling of n-bit symbols, and Lemma 3.3 (both the Case 1 and Case 2 uniform-resampling estimates) is invalid for bitwise flips. The same symbol-resampling model is used in Section 5 (rerandomizing characters), so the intended convention is clear; however, as written, §2.3 states only the binary-alphabet instance, and a reader taking the formula literally would conclude Theorem 3.2 is proved for a different model than the definition. The paper should state the general symbol-alphabet perturbation rule for function oracles explicitly and confirm that Theorem 3.2, Section 5, and Section 6 all refer to it; otherwise the interpretation of the headline separation is ambiguous.
[§4.2, Lemma 4.5; §1.2 AI disclosure] Lemma 4.5 is the averaging engine for Theorem 4.1, and the paper discloses (§1.2) that it was produced with GPT assistance and verified only by hand, with no machine-checked proof. The lemma's proof is an intricate case analysis — the split of the mode-containing interval at m, the regime split |I| >= s+m−b+2 versus m−a+1 < s, the bound p(k) <= C/s, and the anti-concentration application of Lemma 2.5 — and a subtle error in any of these regimes would shift the characterization. I re-derived the main identities (the sqrt(x+y) split, q_f(j), q_f(j+1) >= t_j, the weighted-influence double-counting, min{μ, n−μ} >= (s−1)^2, and the tail estimate Pr[|W−μ|>d/2] <= (n+2)^{-10}) and they check out; no concrete error was found. However, given that this is the load-bearing step of the paper's deepest result, I would like the mode-interval case analysis written out in full, with the interval-containing-m split and the constants in the Lemma 2.5 application made explicit, and preferably one independent verification of that passage, before the characterization is certified.
[Appendix A.5, Lemma A.9 and footnote 7] The reversible simulation of the [AK12] reduction asserts that a fixed deterministic procedure, reading only O(L)-length neighborhoods Rec_X(i) and Rec_Y(j), computes Mate(i,j) exactly as the adaptive [AK12] query procedure would. Footnote 7 asserts this ('the two answers agree exactly when P[i] = Q[j]') but does not demonstrate it; the difficulty is that the identification of the block containing i's offset relies on the separation property of Lemma 4.6 of [AK12], and the tie-breaking and invalidation steps of that proof are adaptive. This exactness claim is load-bearing for the O(L) multiplicative overhead in Corollary 6.4, and consequently for the smoothed edit-distance query bound; if a fixed local procedure cannot reproduce the adaptive answers, the simulation cost needs revisiting. I would like the exactness claim proved in the appendix rather than asserted.

Minor objections (4)

[§2.3] Related to the first major comment: the paper should state that the perturbation model applies to arbitrary alphabets by independently resampling each symbol with probability σ, and that the displayed formula is the binary-alphabet specialization; footnote 2 gestures at this but the main definition does not.
[§6.1, Theorem 6.5 and surrounding text] There are several typographical issues: 'ℓ 1, ℓ 2' with stray spaces in the statements of Theorem 6.5 and the gap-tester discussion, and the expression 'eO((n√ℓ2/(ℓ2−ℓ1))^{2/3})' renders awkwardly. Please clean up the math typography.
[§4.2, eq. (1)] The notation q_{j,σ}(z) with denominator s_σ + dist(z,[j,j+1]) is consistent once one recalls s_σ = 1 + sqrt(nσ(2−σ))/2, but the σ = 0 case would be clearer if the text explicitly noted that dist is in absolute value and that s_0 = 1; currently the definition of dist is implicit.
[§3, paragraph after Theorem 3.2] The sentence 'The quantum worst case complexity of this problem is Ω(2^{n/2})' is justified only by the two-case distinction sketched in the preceding paragraph; a citation to the standard argument or a one-line reduction to unstructured search would make the worst-case claim self-contained.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Measuring query complexity after a small random perturbation of the input reveals quantum speedups that worst-case analysis hides: the total Simon problem becomes quantum-easy while staying classically hard, and one pair of parameters…

The reading

This paper claims that measuring query complexity under small random perturbations — the smoothed-analysis model long used in classical algorithms — exposes quantum advantages that worst-case analysis hides. First, the total (promise-free) Simon problem, which needs $\Omega(2^{n/2})$ quantum queries and $\Omega(2^n)$ randomized queries in the worst case, becomes solvable in $O(n/\sigma)$ smoothed quantum queries while its smoothed classical complexity stays $\Omega(2^{n/2})$; for every $\sigma \ge 1/\mathrm{poly}(n)$ this is an exponential quantum-classical separation. Second, for every symmetric Boolean function the paper pins down both smoothed quantum and randomized complexity up to polylog factors in terms of two parameters, the transition cost and the weighted influence. Third, it gives superpolynomial smoothed quantum speedups for pattern matching and a quantum algorithm for $O(1/\sigma)$-approximate smoothed edit distance, powered by an improved quantum collision-estimation routine. The unifying message is that smoothing — perturbing each input bit with probability $\sigma$, then taking the worst case over original inputs of expected query cost — interpolates between the worst-case results of Beals et al. and the average-case results of Ambainis and de Wolf.

What carries the argument

Three mechanisms carry the argument. For Total Simon, the machine is ordinary Fourier sampling on the perturbed truth table: with probability at least $1 - 2^{-\Omega(n)}$ the $\sigma$-perturbation leaves at least $N\sigma/64$ singleton fibers, each measurement of a singleton fiber yields a Fourier sample uniform over $\mathbb{F}_2^n$, and $t = \Theta(n/\sigma)$ samples certify the absence of a period unless a rare fallback queries the full table. For symmetric functions, the load-bearing objects are the two parameters $\mathrm{transcost}_\sigma(f)$ and $w\mathrm{Inf}_\sigma(f)$, built from the transition set $T(f)$ of adjacent Hamming weights where the value changes, together with Lemma 4.5, an averaging lemma that converts per-weight costs into these two forms: it uses log-concavity of the perturbed-weight distribution and a partition of the Hamming layers into maximal constancy intervals, so that nearby transitions contribute through their total interval probability and endpoint contributions accumulate into the weighted influence. For edit distance, the machinery is a quantum walk on Johnson graphs yielding a gap-sensitive collision tester with $\tilde{O}\big(\big(\frac{n\sqrt{\ell_2}}{\ell_2 - \ell_1}\big)^{2/3}\big)$ queries, bootstrapped to multiplicative and additive collision estimators (improving the $\varepsilon$ dependence from $\varepsilon^{-25/24}$ to $\varepsilon^{-2/3}$), a variable-time approximate-counting primitive, and a reversible subset database that gives oracle access to the implicit Ulam instance while preserving the locality and separation properties of the Andoni–Krauthgamer reduction. The authors disclose that Lemma 4.5 was produced with GPT assistance and hand-verified; there is no machine-checked proof of it or of the reversible reduction.

Extended reading notes

Core claim

The central claim, on the authors' own terms, is twofold. Theorem 3.2 with Lemma 3.4 establishes that there exists a total function — the total version of Simon's problem with no promise — whose smoothed quantum query complexity is $O(n/\sigma)$, exponentially smaller than its smoothed classical query complexity $\Omega(2^{n/2})$, for every $\sigma \ge 1/\mathrm{poly}(n)$; the algorithm is the standard Fourier-sampling primitive for hidden subgroups, and smoothing creates enough singleton fibers to make each Fourier sample uniform and the absence of the period certifiable. Theorem 4.1 then characterizes every total symmetric Boolean function: the smoothed randomized complexity is $\tilde{\Theta}(\min\{n, \mathrm{transcost}_\sigma(f)^2\})$ and the smoothed quantum complexity is $\tilde{\Theta}(w\mathrm{Inf}_\sigma(f) + \mathrm{transcost}_\sigma(f))$, where the transition cost measures the hardest single weight-distinction after accounting for the spread of the perturbed weight and the weighted influence sums per-transition costs weighted by the probabilities of the adjacent Hamming layers. At $\sigma = 0$ this recovers the Beals et al. worst-case characterization and at $\sigma = 1$ the Ambainis–de Wolf average-case results, so the two parameters unify previously separate regimes. For strings, the paper proves superpolynomial smoothed quantum speedups for pattern matching and, combining a new gap-sensitive and multiplicative collision estimator with a reversible implementation of the Andoni–Krauthgamer reduction, a quantum algorithm for $O(1/\sigma)$-approximate smoothed edit distance in $\tilde{O}\big(\frac{1}{\sigma}\big(\frac{n}{R} + \frac{n^{2/3}}{R^{1/3}}\big)\big)$ queries, where $R$ is the edit distance; for $R = \Theta(n)$ this is $\tilde{O}(n^{1/3}/\sigma)$, beating the classical $\tilde{O}(\sqrt{n}/\sigma)$.

Load-bearing premise

The deepest result, Theorem 4.1, collapses if Lemma 4.5 fails: the lemma, disclosed as GPT-assisted and hand-verified rather than machine-checked, is what converts per-Hamming-weight query costs into the $\tilde{\Theta}(\mathrm{transcost}, w\mathrm{Inf})$ forms, and a subtle error in its anti-concentration or interval-partition argument would shift the characterization. The edit-distance result additionally stands on the reversible implementation of the Andoni–Krauthgamer reduction preserving the locality and separation properties needed for the implicit Ulam instance.

Editorial extensions

If this is right

For every $\sigma \ge 1/\mathrm{poly}(n)$ there is a total Boolean function whose smoothed quantum complexity is exponentially smaller than its smoothed classical complexity, so the worst-case polynomial relation between quantum and randomized query complexity for total functions does not survive smoothing.
Theorem 4.1 unifies the field's two classic regimes: $\sigma = 0$ recovers the Beals et al. worst-case characterization and $\sigma = 1$ recovers the Ambainis–de Wolf average-case results for symmetric functions, with intermediate $\sigma$ interpolating between them.
Under full smoothing, Majority becomes $\tilde{\Theta}(\sqrt{n})$ for quantum queries while remaining $\tilde{\Theta}(n)$ for randomized queries — a polynomial quantum speedup that appears only in the smoothed model.
The $O(1/\sigma)$-approximate smoothed edit distance algorithm runs in $\tilde{O}\big(\frac{1}{\sigma}\big(\frac{n}{R} + \frac{n^{2/3}}{R^{1/3}}\big)\big)$ quantum queries, improving the classical $\tilde{O}\big(\frac{1}{\sigma}\big(\frac{n}{R} + \sqrt{n}\big)\big)$ for $R = \omega(\sqrt{n})$, and giving $\tilde{O}(n^{1/3}/\sigma)$ when $R = \Theta(n)$.
The improved collision estimator, with $\varepsilon$ dependence dropping from $\varepsilon^{-25/24}$ to $\varepsilon^{-2/3}$, is a transferable primitive for sublinear quantum algorithms beyond edit distance.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The Total Simon result suggests a general design principle that the paper does not itself state: smoothing may turn standard quantum primitives (Fourier sampling, amplitude estimation) that are exponentially bad in the worst case into efficient procedures, because the noise destroys the fragile structure that created worst-case hardness; a natural test is non-abelian Fourier sampling on smoothed g
Smoothed analysis could serve as a principled middle ground between worst-case and average-case complexity for judging when quantum advantage is 'realistic', and extending it to heuristic quantum algorithms such as QAOA might yield rigorous guarantees where none currently exist — another question the authors leave open.
If Lemma 4.5 holds, the two-parameter characterization implies that smoothed complexity of symmetric functions is computable in polynomial time for any given $\sigma$, making 'how hard is this function under noise' a tractable query — a computational tool the paper does not itself exploit.

Original abstract

Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice. We initiate a systematic study of its quantum counterpart and show the following results. $(1)$ We show that there is a total function whose smoothed quantum query complexity is exponentially smaller than its classical query complexity. $(2)$ We give near-tight characterizations of smoothed randomized and quantum query complexities for symmetric Boolean functions, unifying the worst-case complexity results of [Beals et al, FOCS'98] and average-case complexity results of [Ambainis and de Wolf, STACS'00]. $(3)$ We study string problems such as pattern matching and edit distance and, in various regimes, give polynomial to superpolynomial quantum speedups. Our main technical ingredients include a near-tight quantum algorithm for $\varepsilon$-approximating the number of collisions between two non-repetitive strings, improving the result of Le Gall and Ng [QIC'22]. Together, our results show that smoothing can reveal larger quantum speedups than worst-case analysis suggests, opening a path towards quantum advantage on more realistic inputs.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-29: 1 request, 5,706 input tokens.

What the abstract itself states, as probabilities: claims first 0.57 · states limitation 0.09 · human participants 0.01 · controlled comparison 0.15 · randomized assignment 0.02 · states quantitative result 0.63 · compares with prior results 0.95 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice. We initiate a systematic study of its quantum counterpart and show the following results. $(1)$ We show that there is a total function whose smoothed quantum query complexity is exponentially smaller than its classical query complexity. $(2)$ We give near-tight characterizations of smoothed randomized and quantum query complexities for symmetric Boolean functions, unifying the worst-case complexity results of [Beals et al, FOCS'98] and average-case complexity results of [Ambainis and de Wolf, STACS'00]. $(3)$ We study string problems such as pattern matching and edit distance and, in various regimes, give polynomial to superpolynomial quantum speedups. Our main technical ingredients include a near-tight quantum algorithm for $\varepsilon$-approximating the number of collisions between two non-repetitive strings, improving the result of Le Gall and Ng [QIC'22]. Together, our results show that smoothing can reveal larger quantum speedups than worst-case analysis suggests, opening a path towards quantum advantage on more realistic inputs.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Smoothed analysis is a central framework in classical algorithms for explaining the performance of algorithms beyond the worst case, often explaining why algorithms perform well in practice.	background 1.00	0.03	0.02	asserted 0.99
s1	We initiate a systematic study of its quantum counterpart and show the following results.	contribution 0.99	0.81	0.05	asserted 0.94
s2	$(1)$ We show that there is a total function whose smoothed quantum query complexity is exponentially smaller than its classical query complexity.	result 1.00	0.96	0.22	asserted 1.00
s3	$(2)$ We give near-tight characterizations of smoothed randomized and quantum query complexities for symmetric Boolean functions, unifying the worst-case complexity results of [Beals et al, FOCS'98] and average-case complexity results of [Ambainis and de Wolf, STACS'00].	result 0.96	0.92	0.09	asserted 1.00
s4	$(3)$ We study string problems such as pattern matching and edit distance and, in various regimes, give polynomial to superpolynomial quantum speedups.	result 0.87	0.96	0.06	asserted 1.00
s5	Our main technical ingredients include a near-tight quantum algorithm for $\varepsilon$-approximating the number of collisions between two non-repetitive strings, improving the result of Le Gall and Ng [QIC'22].	method 0.76	0.93	0.04	asserted 1.00
s6	Together, our results show that smoothing can reveal larger quantum speedups than worst-case analysis suggests, opening a path towards quantum advantage on more realistic inputs.	interpretation 1.00	0.81	0.93	asserted 0.92

What kind of paper the classifier reports this is: theoretical result 0.99 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Works cited (127)

[1]

Alexandr Andoni, Haitham Hassanieh, Piotr Indyk, and Dina Katabi. Shift finding in sub-linear time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 457--465. SIAM, 2013

View on Pith 2013
[2]

Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelh \"o fer, and Miklos Santha. Classical and quantum algorithms for variants of subset-sum via dynamic programming. In Proceedings of the 30th Annual European Symposium on Algorithms (ESA 2022) , volume 244, pages 6:1--6:18, 2022

View on Pith 2022
[3]

Alexandr Andoni and Robert Krauthgamer. The smoothed complexity of edit distance. ACM Transactions on Algorithms (TALG) , 8(4):1--25, 2012. https://www.mit.edu/ andoni/papers/smoothTALG.pdf

View on Pith 2012
[4]

Andris Ambainis. Quantum search with variable times. Theory of Computing Systems , 47(3):786--807, 2010

View on Pith 2010
[5]

David Arthur, Bodo Manthey, and Heiko R \"o glin. Smoothed analysis of the k -means method. Journal of the ACM , 58(5):19:1--19:31, 2011

View on Pith 2011
[6]

Alexandr Andoni and Huy L. Nguyen. Near-optimal sublinear time algorithms for ulam distance. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms , USA, 2010. Society for Industrial and Applied Mathematics

View on Pith 2010
[7]

Alexandr Andoni and Negev Shekel Nosatzki. Edit distance in near-linear time: it's a constant factor. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science , pages 990--1001, 2020

View on Pith 2020
[8]

Graeme Auld and Kritsana Neammanee. A nonuniform local limit theorem for poisson binomial random variables via stein's method. Journal of Inequalities and Applications , 2024(1):10, 2024

View on Pith 2024
[9]

Andris Ambainis and Ronald de Wolf . Average-case quantum query complexity. Journal of Physics A: Mathematical and General , 34(35):6741, 2001

View on Pith 2001
[10]

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald De Wolf. Quantum lower bounds by polynomials. Journal of the ACM (JACM) , 48(4):778--797, 2001

View on Pith 2001
[11]

Aleksandrs Belovs, Gilles Brassard, Peter H yer, Marc Kaplan, Sophie Laplante, and Louis Salvail. Provably secure key establishment against quantum adversaries. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017) , volume 73 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 3:1--3:17. Schlo...

View on Pith 2017
[12]

Aditya Bhaskara, Moses Charikar, Ankur Moitra, and Aravindan Vijayaraghavan. Smoothed analysis of tensor decompositions. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC) , pages 594--603, 2014

View on Pith 2014
[13]

Xavier Bonnetain, Andr \' e Chailloux, Andr \' e Schrottenloher, and Yixin Shen. Finding many collisions via reusable quantum walks - application to lattice sieving. In Proceedings of the 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, , volume 14008, pages 221--251, 2023

View on Pith 2023
[15]

Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC) , pages 51--58, 2015

View on Pith 2015
[16]

Xavier Bonnetain, Johanna Loyer, André Schrottenloher, and Yixin Shen. A tight quantum algorithm for multiple collision search. Cryptology ePrint Archive, Paper 2025/1690, 2025

View on Pith 2025
[17]

Harry Buhrman, Subhasree Patro, and Florian Speelman. A Framework of Quantum Strong Exponential-Time Hypotheses . In Markus Bl\" a ser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) , volume 187 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 19:1--19:19, Dagstuhl, G...

View on Pith 2021
[19]

Xi Chen, Anindya De, Chin Ho Lee, Rocco A Servedio, and Sandip Sinha. Polynomial-time trace reconstruction in the smoothed complexity model. ACM Transactions on Algorithms (TALG) , 2020

View on Pith 2020
[20]

Xi Chen, Anindya De, Chin Ho Lee, Rocco A Servedio, and Sandip Sinha. Near-optimal average-case approximate trace reconstruction from few traces. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 779--821. SIAM, 2022

View on Pith 2022
[21]

J. N. Darroch. On the distribution of the number of successes in independent trials. The Annals of Mathematical Statistics , 35(3):1317--1321, 1964

View on Pith 1964
[22]

Daniel Dadush and Sophie Huiberts. A friendly smoothed analysis of the simplex method. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 390--403, 2018

View on Pith 2018
[23]

Michael Etscheid and Heiko R \"o glin. Smoothed analysis of local search for the maximum-cut problem. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 882--889, 2014

View on Pith 2014
[24]

Fran c ois Le Gall. Improved quantum algorithm for triangle finding via combinatorial arguments. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 216--225, 2014

View on Pith 2014
[25]

Rong Ge, Qingqing Huang, and Sham M. Kakade. Learning mixtures of gaussians in high dimensions. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC) , pages 761--770, 2015

View on Pith 2015
[26]

\ Fran c ois Le\ Gall and \ Iu Iong\ Ng. Quantum approximate counting for markov chains and application to collision counting. Quantum Information and Computation , 22(15-16):1261--1279, November 2022. Publisher Copyright: Rinton Press

View on Pith 2022
[27]

Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the ACM Symposium on Theory of Computing (STOC 1996) , pages 212--219. ACM , 1996

View on Pith 1996
[28]

András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: E xponential improvements for quantum matrix arithmetics. In STOC 51st , pages 193--204, 2019. Full version in arxiv 1806.01838

View on Pith Pith review arXiv 2019
[29]

Ramesh Hariharan and V. Vinay. String matching in O ( n + m ) quantum time. Journal of Discrete Algorithms , 1(1):103--110, 2003

View on Pith 2003
[30]

Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences , 62(2):367--375, 2001

View on Pith 2001
[31]

Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences , 63(4):512--530, 2001

View on Pith 2001
[32]

Stacey Jeffery. Quantum subroutine composition, 2022. arXiv:2209.14146

View on Pith Pith review arXiv 2022
[33]

Nathaniel Johnston, Benjamin Lovitz, and Aravindan Vijayaraghavan. Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1316--1336. IEEE, 2023

View on Pith 2023
[35]

Adam Tauman Kalai, Alex Samorodnitsky, and Shang-Hua Teng. Learning and smoothed analysis. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 395--404, 2009

View on Pith 2009
[36]

Fran c ois Le Gall and Saeed Seddighin. Quantum meets fine-grained complexity: Sublinear time quantum algorithms for string problems. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2022

View on Pith 2022
[37]

Fr \'e d \'e ric Magniez, Ashwin Nayak, J \'e r \'e mie Roland, and Miklos Santha. Search via quantum walk. SIAM Journal on Computing , 40(1):142--164, 2011

View on Pith 2011
[38]

Ashley Montanaro. Quantum pattern matching fast on average. Algorithmica , 77(1):16--39, 2017

View on Pith 2017
[39]

Xiao Mao and Aviad Rubinstein. Approximation schemes for edit distance and lcs in quasi-strongly subquadratic time. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing , page 744–754, 2026

View on Pith 2026
[40]

Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of the thirty-first annual ACM symposium on Theory of computing , pages 384--393, 1999

View on Pith 1999
[41]

Supartha Podder, Penghui Yao, and Zekun Ye. On the fine-grained query complexity of symmetric functions. Information and Computation , 299:102145, 2025

View on Pith 2025
[42]

Heiko R \"o glin and Shang-Hua Teng. Smoothed analysis of multiobjective optimization. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 681--690, 2009

View on Pith 2009
[43]

Heiko R \"o glin and Berthold V \"o cking. Smoothed analysis of integer programming. Mathematical Programming , 110(1):21--56, 2007

View on Pith 2007
[44]

Daniel R. Simon. On the power of quantum computation. SIAM Journal on Computing , 26(5):1474--1483, 1997

View on Pith 1997
[45]

Arvind Sankar, Daniel A. Spielman, and Shang-Hua Teng. Smoothed analysis of the condition numbers and growth factors of matrices. SIAM Journal on Matrix Analysis and Applications , 28(2):446--476, 2006

View on Pith 2006
[46]

Daniel A Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM) , 51(3):385--463, 2004

View on Pith 2004
[47]

Daniel A Spielman and S-H Teng. Smoothed analysis of algorithms and heuristics. London Mathematical Society Lecture Note Series , 1(331):274--342, 2006

View on Pith 2006
[48]

Andrew Chi-Chih Yao. The complexity of pattern matching for a random string. SIAM Journal on Computing , 8(3):368--387, 1979

View on Pith 1979
[50]

Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang. Fixed-point quantum search with an optimal number of queries. prl , 113(21):210501, 2014. arxiv 1409.3305

View on Pith Pith review arXiv 2014
[51]

Zhikuan Zhao, Jack K Fitzsimons, Patrick Rebentrost, Vedran Dunjko, and Joseph F Fitzsimons. Smooth input preparation for quantum and quantum-inspired machine learning. Quantum Machine Intelligence , 3(1):14, 2021

View on Pith 2021
[52]

The smoothed complexity of edit distance , author=. ACM Transactions on Algorithms (TALG) , volume=. 2012 , publisher=

View on Pith 2012
[53]

Quantum amplitude amplification and estimation , author=. arXiv preprint quant-ph/0005055 , year=

View on Pith Pith review arXiv
[54]

Certifying entanglement dimensionality by random Pauli sampling , author=. arXiv preprint arXiv:2601.11040 , year=

View on Pith Pith review arXiv
[55]

Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond , author=. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2023 , organization=

View on Pith 2023
[56]

The quantum query complexity of approximating the median and related statistics , author=. Proceedings of the thirty-first annual ACM symposium on Theory of computing , pages=

View on Pith
[57]

On the fine-grained query complexity of symmetric functions , author=. computational complexity , volume=. 2025 , publisher=

View on Pith 2025
[58]

Near-optimal quantum algorithms for string problems , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

View on Pith 2022
[59]

Average-case quantum query complexity , author=. Journal of Physics A: Mathematical and General , volume=. 2001 , publisher=

View on Pith 2001
[60]

Optimal Bounds for Noisy Sorting , author=. arXiv preprint arXiv:2302.12440 , year=

View on Pith Pith review arXiv
[61]

Smoothed analysis of algorithms and heuristics , author=. London Mathematical Society Lecture Note Series , volume=. 2006 , publisher=

View on Pith 2006
[62]

A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions , author=. arXiv preprint arXiv:0802.1816 , year=

View on Pith Pith review arXiv
[63]

Improved Quantum Query Complexity on Easier Inputs , author=. arXiv:2303.00217 , year=

View on Pith Pith review arXiv
[64]

Arvind Sankar and Daniel A. Spielman and Shang-Hua Teng , title =. SIAM Journal on Matrix Analysis and Applications , volume =. 2006 , doi =

View on Pith 2006
[65]

Heiko R. Smoothed Analysis of Integer Programming , journal =. 2007 , doi =

View on Pith 2007
[66]

Adam Tauman Kalai and Alex Samorodnitsky and Shang-Hua Teng , title =. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages =. 2009 , doi =

View on Pith 2009
[67]

Heiko R. Smoothed Analysis of Multiobjective Optimization , booktitle =. 2009 , doi =

View on Pith 2009
[68]

David Arthur and Bodo Manthey and Heiko R. Smoothed Analysis of the. Journal of the ACM , volume =. 2011 , doi =

View on Pith 2011
[69]

Michael Etscheid and Heiko R. Smoothed Analysis of Local Search for the Maximum-Cut Problem , booktitle =. 2014 , doi =

View on Pith 2014
[70]

Aditya Bhaskara and Moses Charikar and Ankur Moitra and Aravindan Vijayaraghavan , title =. Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC) , pages =. 2014 , doi =

View on Pith 2014
[71]

Rong Ge and Qingqing Huang and Sham M. Kakade , title =. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC) , pages =. 2015 , doi =

View on Pith 2015
[72]

Approximating edit distance in truly subquadratic time: Quantum and mapreduce , author=. Journal of the ACM (JACM) , volume=. 2021 , publisher=

View on Pith 2021
[73]

Near-optimal average-case approximate trace reconstruction from few traces , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

View on Pith 2022
[74]

Polynomial-time trace reconstruction in the smoothed complexity model , author=. ACM Transactions on Algorithms (TALG) , year=

View on Pith
[75]

Quantum lower bounds by polynomials , author=. Journal of the ACM (JACM) , volume=. 2001 , publisher=

View on Pith 2001
[76]

Nikhil Vyas and Ryan Williams , editor =. On Oracles and Algorithmic Methods for Proving Lower Bounds , booktitle =

View on Pith
[77]

Approximating edit distance within constant factor in truly sub-quadratic time , author=. Journal of the ACM (JACM) , volume=. 2020 , publisher=

View on Pith 2020
[78]

Normal subgroup reconstruction and quantum computation using group representations , author=. Proceedings of the thirty-second annual ACM symposium on Theory of computing , pages=

View on Pith
[79]

Efficiently approximating edit distance between pseudorandom strings , author=. Proceedings of the thirtieth annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2019 , organization=

View on Pith 2019
[80]

The hidden subgroup problem-review and open problems , author=. arXiv preprint quant-ph/0411037 , year=

View on Pith Pith review arXiv
[81]

Quantum meets fine-grained complexity: Sublinear time quantum algorithms for string problems , author=. 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , year=

View on Pith 2022
[82]

Shift finding in sub-linear time , author=. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2013 , organization=

View on Pith 2013
[83]

A subexponential-time quantum algorithm for the dihedral hidden subgroup problem , author=. SIAM Journal on Computing , volume=. 2005 , publisher=

View on Pith 2005
[84]

Quantum algorithm for the Boolean hidden shift problem , author=. International Computing and Combinatorics Conference , pages=. 2011 , organization=

View on Pith 2011
[85]

Quantum pattern matching fast on average , author=. Algorithmica , volume=. 2017 , publisher=

View on Pith 2017
[86]

Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time , author=. Journal of the ACM (JACM) , volume=. 2004 , publisher=

View on Pith 2004
[87]

A friendly smoothed analysis of the simplex method , author=. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages=

View on Pith
[88]

Complexity measures and decision tree complexity: a survey , author=. Theoretical Computer Science , volume=. 2002 , publisher=

View on Pith 2002
[89]

Reduction from non-injective hidden shift problem to injective hidden shift problem , author=. arXiv:1207.4537 , year=

View on Pith Pith review arXiv
[90]

Ambainis, Andris , title =. SIAM Journal on Computing , volume =. 2007 , doi =

View on Pith 2007
[91]

Xavier Bonnetain and Johanna Loyer and André Schrottenloher and Yixin Shen , title =. 2025 , url =

View on Pith 2025
[92]

Gall, \ Fran c ois Le\ and Ng, \ Iu Iong\. QUANTUM APPROXIMATE COUNTING FOR MARKOV CHAINS AND APPLICATION TO COLLISION COUNTING. Quantum Information and Computation. 2022. doi:10.26421/QIC22.15-16-1

View on Pith doi:10.26421/qic22.15-16-1 2022
[93]

Knuth, Donald E. and Morris, Jr., James H. and Pratt, Vaughan R. , title =. SIAM Journal on Computing , volume =. 1977 , doi =

View on Pith 1977
[94]

Ramesh Hariharan and V. Vinay , title =. Journal of Discrete Algorithms , volume =. 2003 , doi =

View on Pith 2003
[95]

Yao, Andrew Chi-Chih , title =. SIAM Journal on Computing , volume =. 1979 , doi =

View on Pith 1979
[96]

Andrew M. Childs and Robin Kothari and Maris Ozols and Martin Roetteler , title =. 8th Conference on the Theory of Quantum Computation, Communication and Cryptography,. 2013 , doi =

View on Pith 2013
[97]

Qisheng Wang and Mingsheng Ying , title =. Theory of Computing Systems , volume =. 2024 , doi =

View on Pith 2024
[98]

Andoni, Alexandr and Nguyen, Huy L. , title =. 2010 , isbn =

View on Pith 2010
[99]

András Gilyén and Yuan Su and Guang Hao Low and Nathan Wiebe , booktitle =. Quantum singular value transformation and beyond:. 2019 , pages =. doi:10.1145/3313276.3316366 , note =

View on Pith arXiv 2019
[100]

Fixed-Point Quantum Search with an Optimal Number of Queries , author =. prl , volume =. 2014 , doi =

View on Pith 2014
[101]

Gilles Brassard and Peter H. Quantum Amplitude Amplification and Estimation , BOOKTITLE =. 2002 , doi =

View on Pith 2002
[102]

Bernstein, Sergei , journal=. On a modification of

View on Pith
[103]

High-Dimensional Statistics: A Non-Asymptotic Viewpoint , author=. 2019 , publisher=

View on Pith 2019
[104]

Allcock, Jonathan and Hamoudi, Yassine and Joux, Antoine and Klingelh. Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming , booktitle =. 2022 , volume =

View on Pith 2022
[105]

Xavier Bonnetain and Andr. Finding Many Collisions via Reusable Quantum Walks - Application to Lattice Sieving , booktitle =. 2023 , doi =

View on Pith 2023
[106]

A log-depth in-place quantum Fourier transform that rarely needs ancillas , author=. arXiv preprint arXiv:2505.00701 , year=

View on Pith Pith review arXiv
[107]

Approximate quantum Fourier transform in logarithmic depth on a line , author=. arXiv preprint arXiv:2504.20832 , year=

View on Pith Pith review arXiv
[108]

Smooth input preparation for quantum and quantum-inspired machine learning , author=. Quantum Machine Intelligence , volume=. 2021 , publisher=

View on Pith 2021
[109]

Stacey Jeffery , title =

View on Pith
[110]

Ambainis, Andris , title =. Theory of Computing Systems , volume =. 2010 , publisher =

View on Pith 2010
[111]

Alexandr Andoni and Negev Shekel Nosatzki , title =. Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science , pages =. 2020 , doi =

View on Pith 2020
[112]

Mao, Xiao and Rubinstein, Aviad , title =. Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages =. 2026 , doi =

View on Pith 2026
[113]

On the Complexity of k-SAT , journal =. 2001 , issn =. doi:https://doi.org/10.1006/jcss.2000.1727 , url =

View on Pith arXiv 2001
[114]

Which Problems Have Strongly Exponential Complexity? , journal =. 2001 , issn =. doi:https://doi.org/10.1006/jcss.2001.1774 , url =

View on Pith arXiv 2001
[115]

On the Fine-Grained Query Complexity of Symmetric Functions , author=. Information and Computation , volume=. 2025 , publisher=

View on Pith 2025
[116]

Daniel R. Simon , title =. SIAM Journal on Computing , volume =. 1997 , publisher =

View on Pith 1997
[117]

Fran. Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments , booktitle =. 2014 , doi =

View on Pith 2014
[118]

Stacey Jeffery , title =. 2022 , note =

View on Pith 2022
[119]

Andris Ambainis , title =. Theory of Computing Systems , volume =. 2010 , doi =

View on Pith 2010
[120]

Buhrman, Harry and Patro, Subhasree and Speelman, Florian , title =. 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) , pages =. 2021 , volume =. doi:10.4230/LIPIcs.STACS.2021.19 , annote =

View on Pith doi:10.4230/lipics.stacs.2021.19 2021
[121]

Arturs Backurs and Piotr Indyk , title =. Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC) , pages =. 2015 , doi =

View on Pith 2015
[122]

Lov K. Grover , title =. Proceedings of the. 1996 , doi =

View on Pith 1996
[123]

Fr. Search via Quantum Walk , journal =. 2011 , doi =

View on Pith 2011
[124]

Herman Chernoff , title =. 1952 , journal =

View on Pith 1952
[125]

Mitzenmacher, Michael and Upfal, Eli , title =. 2005 , publisher =

View on Pith 2005
[126]

Peter H. Negative Weights Make Adversaries Stronger , booktitle =

View on Pith
[127]

Howard Barnum and Michael Saks and Mario Szegedy , title =. Proceedings of the 18th IEEE Conference on Computational Complexity (CCC) , pages =. 2003 , doi =

View on Pith 2003
[128]

Aleksandrs Belovs and Gilles Brassard and Peter H. Provably Secure Key Establishment Against Quantum Adversaries , booktitle =. 2018 , publisher =

View on Pith 2018
[129]

Graeme Auld and Kritsana Neammanee , title =. Journal of Inequalities and Applications , volume =. 2024 , doi =

View on Pith 2024
[130]

Darroch, J. N. , title =. The Annals of Mathematical Statistics , volume =. 1964 , doi =

View on Pith 1964
[131]

Kuszmaul, William , title =. 2019 , booktitle =

View on Pith 2019

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

Alexandr Andoni, Haitham Hassanieh, Piotr Indyk, and Dina Katabi. Shift finding in sub-linear time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms , pages 457--465. SIAM, 2013

View on Pith 2013

[2] [2]

Jonathan Allcock, Yassine Hamoudi, Antoine Joux, Felix Klingelh \"o fer, and Miklos Santha. Classical and quantum algorithms for variants of subset-sum via dynamic programming. In Proceedings of the 30th Annual European Symposium on Algorithms (ESA 2022) , volume 244, pages 6:1--6:18, 2022

View on Pith 2022

[3] [3]

Alexandr Andoni and Robert Krauthgamer. The smoothed complexity of edit distance. ACM Transactions on Algorithms (TALG) , 8(4):1--25, 2012. https://www.mit.edu/ andoni/papers/smoothTALG.pdf

View on Pith 2012

[4] [4]

Andris Ambainis. Quantum search with variable times. Theory of Computing Systems , 47(3):786--807, 2010

View on Pith 2010

[5] [5]

David Arthur, Bodo Manthey, and Heiko R \"o glin. Smoothed analysis of the k -means method. Journal of the ACM , 58(5):19:1--19:31, 2011

View on Pith 2011

[6] [6]

Alexandr Andoni and Huy L. Nguyen. Near-optimal sublinear time algorithms for ulam distance. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms , USA, 2010. Society for Industrial and Applied Mathematics

View on Pith 2010

[7] [7]

Alexandr Andoni and Negev Shekel Nosatzki. Edit distance in near-linear time: it's a constant factor. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science , pages 990--1001, 2020

View on Pith 2020

[8] [8]

Graeme Auld and Kritsana Neammanee. A nonuniform local limit theorem for poisson binomial random variables via stein's method. Journal of Inequalities and Applications , 2024(1):10, 2024

View on Pith 2024

[9] [9]

Andris Ambainis and Ronald de Wolf . Average-case quantum query complexity. Journal of Physics A: Mathematical and General , 34(35):6741, 2001

View on Pith 2001

[10] [10]

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald De Wolf. Quantum lower bounds by polynomials. Journal of the ACM (JACM) , 48(4):778--797, 2001

View on Pith 2001

[11] [11]

Aleksandrs Belovs, Gilles Brassard, Peter H yer, Marc Kaplan, Sophie Laplante, and Louis Salvail. Provably secure key establishment against quantum adversaries. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017) , volume 73 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 3:1--3:17. Schlo...

View on Pith 2017

[12] [12]

Aditya Bhaskara, Moses Charikar, Ankur Moitra, and Aravindan Vijayaraghavan. Smoothed analysis of tensor decompositions. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC) , pages 594--603, 2014

View on Pith 2014

[13] [13]

Xavier Bonnetain, Andr \' e Chailloux, Andr \' e Schrottenloher, and Yixin Shen. Finding many collisions via reusable quantum walks - application to lattice sieving. In Proceedings of the 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, , volume 14008, pages 221--251, 2023

View on Pith 2023

[14] [15]

Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC) , pages 51--58, 2015

View on Pith 2015

[15] [16]

Xavier Bonnetain, Johanna Loyer, André Schrottenloher, and Yixin Shen. A tight quantum algorithm for multiple collision search. Cryptology ePrint Archive, Paper 2025/1690, 2025

View on Pith 2025

[16] [17]

Harry Buhrman, Subhasree Patro, and Florian Speelman. A Framework of Quantum Strong Exponential-Time Hypotheses . In Markus Bl\" a ser and Benjamin Monmege, editors, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) , volume 187 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 19:1--19:19, Dagstuhl, G...

View on Pith 2021

[17] [19]

Xi Chen, Anindya De, Chin Ho Lee, Rocco A Servedio, and Sandip Sinha. Polynomial-time trace reconstruction in the smoothed complexity model. ACM Transactions on Algorithms (TALG) , 2020

View on Pith 2020

[18] [20]

Xi Chen, Anindya De, Chin Ho Lee, Rocco A Servedio, and Sandip Sinha. Near-optimal average-case approximate trace reconstruction from few traces. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 779--821. SIAM, 2022

View on Pith 2022

[19] [21]

J. N. Darroch. On the distribution of the number of successes in independent trials. The Annals of Mathematical Statistics , 35(3):1317--1321, 1964

View on Pith 1964

[20] [22]

Daniel Dadush and Sophie Huiberts. A friendly smoothed analysis of the simplex method. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 390--403, 2018

View on Pith 2018

[21] [23]

Michael Etscheid and Heiko R \"o glin. Smoothed analysis of local search for the maximum-cut problem. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 882--889, 2014

View on Pith 2014

[22] [24]

Fran c ois Le Gall. Improved quantum algorithm for triangle finding via combinatorial arguments. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 216--225, 2014

View on Pith 2014

[23] [25]

Rong Ge, Qingqing Huang, and Sham M. Kakade. Learning mixtures of gaussians in high dimensions. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC) , pages 761--770, 2015

View on Pith 2015

[24] [26]

\ Fran c ois Le\ Gall and \ Iu Iong\ Ng. Quantum approximate counting for markov chains and application to collision counting. Quantum Information and Computation , 22(15-16):1261--1279, November 2022. Publisher Copyright: Rinton Press

View on Pith 2022

[25] [27]

Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the ACM Symposium on Theory of Computing (STOC 1996) , pages 212--219. ACM , 1996

View on Pith 1996

[26] [28]

András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: E xponential improvements for quantum matrix arithmetics. In STOC 51st , pages 193--204, 2019. Full version in arxiv 1806.01838

View on Pith Pith review arXiv 2019

[27] [29]

Ramesh Hariharan and V. Vinay. String matching in O ( n + m ) quantum time. Journal of Discrete Algorithms , 1(1):103--110, 2003

View on Pith 2003

[28] [30]

Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences , 62(2):367--375, 2001

View on Pith 2001

[29] [31]

Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences , 63(4):512--530, 2001

View on Pith 2001

[30] [32]

Stacey Jeffery. Quantum subroutine composition, 2022. arXiv:2209.14146

View on Pith Pith review arXiv 2022

[31] [33]

Nathaniel Johnston, Benjamin Lovitz, and Aravindan Vijayaraghavan. Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1316--1336. IEEE, 2023

View on Pith 2023

[32] [35]

Adam Tauman Kalai, Alex Samorodnitsky, and Shang-Hua Teng. Learning and smoothed analysis. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 395--404, 2009

View on Pith 2009

[33] [36]

Fran c ois Le Gall and Saeed Seddighin. Quantum meets fine-grained complexity: Sublinear time quantum algorithms for string problems. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) . Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2022

View on Pith 2022

[34] [37]

Fr \'e d \'e ric Magniez, Ashwin Nayak, J \'e r \'e mie Roland, and Miklos Santha. Search via quantum walk. SIAM Journal on Computing , 40(1):142--164, 2011

View on Pith 2011

[35] [38]

Ashley Montanaro. Quantum pattern matching fast on average. Algorithmica , 77(1):16--39, 2017

View on Pith 2017

[36] [39]

Xiao Mao and Aviad Rubinstein. Approximation schemes for edit distance and lcs in quasi-strongly subquadratic time. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing , page 744–754, 2026

View on Pith 2026

[37] [40]

Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of the thirty-first annual ACM symposium on Theory of computing , pages 384--393, 1999

View on Pith 1999

[38] [41]

Supartha Podder, Penghui Yao, and Zekun Ye. On the fine-grained query complexity of symmetric functions. Information and Computation , 299:102145, 2025

View on Pith 2025

[39] [42]

Heiko R \"o glin and Shang-Hua Teng. Smoothed analysis of multiobjective optimization. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 681--690, 2009

View on Pith 2009

[40] [43]

Heiko R \"o glin and Berthold V \"o cking. Smoothed analysis of integer programming. Mathematical Programming , 110(1):21--56, 2007

View on Pith 2007

[41] [44]

Daniel R. Simon. On the power of quantum computation. SIAM Journal on Computing , 26(5):1474--1483, 1997

View on Pith 1997

[42] [45]

Arvind Sankar, Daniel A. Spielman, and Shang-Hua Teng. Smoothed analysis of the condition numbers and growth factors of matrices. SIAM Journal on Matrix Analysis and Applications , 28(2):446--476, 2006

View on Pith 2006

[43] [46]

Daniel A Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM (JACM) , 51(3):385--463, 2004

View on Pith 2004

[44] [47]

Daniel A Spielman and S-H Teng. Smoothed analysis of algorithms and heuristics. London Mathematical Society Lecture Note Series , 1(331):274--342, 2006

View on Pith 2006

[45] [48]

Andrew Chi-Chih Yao. The complexity of pattern matching for a random string. SIAM Journal on Computing , 8(3):368--387, 1979

View on Pith 1979

[46] [50]

Theodore J. Yoder, Guang Hao Low, and Isaac L. Chuang. Fixed-point quantum search with an optimal number of queries. prl , 113(21):210501, 2014. arxiv 1409.3305

View on Pith Pith review arXiv 2014

[47] [51]

Zhikuan Zhao, Jack K Fitzsimons, Patrick Rebentrost, Vedran Dunjko, and Joseph F Fitzsimons. Smooth input preparation for quantum and quantum-inspired machine learning. Quantum Machine Intelligence , 3(1):14, 2021

View on Pith 2021

[48] [52]

The smoothed complexity of edit distance , author=. ACM Transactions on Algorithms (TALG) , volume=. 2012 , publisher=

View on Pith 2012

[49] [53]

Quantum amplitude amplification and estimation , author=. arXiv preprint quant-ph/0005055 , year=

View on Pith Pith review arXiv

[50] [54]

Certifying entanglement dimensionality by random Pauli sampling , author=. arXiv preprint arXiv:2601.11040 , year=

View on Pith Pith review arXiv

[51] [55]

Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond , author=. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2023 , organization=

View on Pith 2023

[52] [56]

The quantum query complexity of approximating the median and related statistics , author=. Proceedings of the thirty-first annual ACM symposium on Theory of computing , pages=

View on Pith

[53] [57]

On the fine-grained query complexity of symmetric functions , author=. computational complexity , volume=. 2025 , publisher=

View on Pith 2025

[54] [58]

Near-optimal quantum algorithms for string problems , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

View on Pith 2022

[55] [59]

Average-case quantum query complexity , author=. Journal of Physics A: Mathematical and General , volume=. 2001 , publisher=

View on Pith 2001

[56] [60]

Optimal Bounds for Noisy Sorting , author=. arXiv preprint arXiv:2302.12440 , year=

View on Pith Pith review arXiv

[57] [61]

Smoothed analysis of algorithms and heuristics , author=. London Mathematical Society Lecture Note Series , volume=. 2006 , publisher=

View on Pith 2006

[58] [62]

A note on quantum algorithms and the minimal degree of epsilon-error polynomials for symmetric functions , author=. arXiv preprint arXiv:0802.1816 , year=

View on Pith Pith review arXiv

[59] [63]

Improved Quantum Query Complexity on Easier Inputs , author=. arXiv:2303.00217 , year=

View on Pith Pith review arXiv

[60] [64]

Arvind Sankar and Daniel A. Spielman and Shang-Hua Teng , title =. SIAM Journal on Matrix Analysis and Applications , volume =. 2006 , doi =

View on Pith 2006

[61] [65]

Heiko R. Smoothed Analysis of Integer Programming , journal =. 2007 , doi =

View on Pith 2007

[62] [66]

Adam Tauman Kalai and Alex Samorodnitsky and Shang-Hua Teng , title =. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages =. 2009 , doi =

View on Pith 2009

[63] [67]

Heiko R. Smoothed Analysis of Multiobjective Optimization , booktitle =. 2009 , doi =

View on Pith 2009

[64] [68]

David Arthur and Bodo Manthey and Heiko R. Smoothed Analysis of the. Journal of the ACM , volume =. 2011 , doi =

View on Pith 2011

[65] [69]

Michael Etscheid and Heiko R. Smoothed Analysis of Local Search for the Maximum-Cut Problem , booktitle =. 2014 , doi =

View on Pith 2014

[66] [70]

Aditya Bhaskara and Moses Charikar and Ankur Moitra and Aravindan Vijayaraghavan , title =. Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing (STOC) , pages =. 2014 , doi =

View on Pith 2014

[67] [71]

Rong Ge and Qingqing Huang and Sham M. Kakade , title =. Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC) , pages =. 2015 , doi =

View on Pith 2015

[68] [72]

Approximating edit distance in truly subquadratic time: Quantum and mapreduce , author=. Journal of the ACM (JACM) , volume=. 2021 , publisher=

View on Pith 2021

[69] [73]

Near-optimal average-case approximate trace reconstruction from few traces , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

View on Pith 2022

[70] [74]

Polynomial-time trace reconstruction in the smoothed complexity model , author=. ACM Transactions on Algorithms (TALG) , year=

View on Pith

[71] [75]

Quantum lower bounds by polynomials , author=. Journal of the ACM (JACM) , volume=. 2001 , publisher=

View on Pith 2001

[72] [76]

Nikhil Vyas and Ryan Williams , editor =. On Oracles and Algorithmic Methods for Proving Lower Bounds , booktitle =

View on Pith

[73] [77]

Approximating edit distance within constant factor in truly sub-quadratic time , author=. Journal of the ACM (JACM) , volume=. 2020 , publisher=

View on Pith 2020

[74] [78]

Normal subgroup reconstruction and quantum computation using group representations , author=. Proceedings of the thirty-second annual ACM symposium on Theory of computing , pages=

View on Pith

[75] [79]

Efficiently approximating edit distance between pseudorandom strings , author=. Proceedings of the thirtieth annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2019 , organization=

View on Pith 2019

[76] [80]

The hidden subgroup problem-review and open problems , author=. arXiv preprint quant-ph/0411037 , year=

View on Pith Pith review arXiv

[77] [81]

Quantum meets fine-grained complexity: Sublinear time quantum algorithms for string problems , author=. 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , year=

View on Pith 2022

[78] [82]

Shift finding in sub-linear time , author=. Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2013 , organization=

View on Pith 2013

[79] [83]

A subexponential-time quantum algorithm for the dihedral hidden subgroup problem , author=. SIAM Journal on Computing , volume=. 2005 , publisher=

View on Pith 2005

[80] [84]

Quantum algorithm for the Boolean hidden shift problem , author=. International Computing and Combinatorics Conference , pages=. 2011 , organization=

View on Pith 2011

[81] [85]

Quantum pattern matching fast on average , author=. Algorithmica , volume=. 2017 , publisher=

View on Pith 2017

[82] [86]

Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time , author=. Journal of the ACM (JACM) , volume=. 2004 , publisher=

View on Pith 2004

[83] [87]

A friendly smoothed analysis of the simplex method , author=. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages=

View on Pith

[84] [88]

Complexity measures and decision tree complexity: a survey , author=. Theoretical Computer Science , volume=. 2002 , publisher=

View on Pith 2002

[85] [89]

Reduction from non-injective hidden shift problem to injective hidden shift problem , author=. arXiv:1207.4537 , year=

View on Pith Pith review arXiv

[86] [90]

Ambainis, Andris , title =. SIAM Journal on Computing , volume =. 2007 , doi =

View on Pith 2007

[87] [91]

Xavier Bonnetain and Johanna Loyer and André Schrottenloher and Yixin Shen , title =. 2025 , url =

View on Pith 2025

[88] [92]

Gall, \ Fran c ois Le\ and Ng, \ Iu Iong\. QUANTUM APPROXIMATE COUNTING FOR MARKOV CHAINS AND APPLICATION TO COLLISION COUNTING. Quantum Information and Computation. 2022. doi:10.26421/QIC22.15-16-1

View on Pith doi:10.26421/qic22.15-16-1 2022

[89] [93]

Knuth, Donald E. and Morris, Jr., James H. and Pratt, Vaughan R. , title =. SIAM Journal on Computing , volume =. 1977 , doi =

View on Pith 1977

[90] [94]

Ramesh Hariharan and V. Vinay , title =. Journal of Discrete Algorithms , volume =. 2003 , doi =

View on Pith 2003

[91] [95]

Yao, Andrew Chi-Chih , title =. SIAM Journal on Computing , volume =. 1979 , doi =

View on Pith 1979

[92] [96]

Andrew M. Childs and Robin Kothari and Maris Ozols and Martin Roetteler , title =. 8th Conference on the Theory of Quantum Computation, Communication and Cryptography,. 2013 , doi =

View on Pith 2013

[93] [97]

Qisheng Wang and Mingsheng Ying , title =. Theory of Computing Systems , volume =. 2024 , doi =

View on Pith 2024

[94] [98]

Andoni, Alexandr and Nguyen, Huy L. , title =. 2010 , isbn =

View on Pith 2010

[95] [99]

András Gilyén and Yuan Su and Guang Hao Low and Nathan Wiebe , booktitle =. Quantum singular value transformation and beyond:. 2019 , pages =. doi:10.1145/3313276.3316366 , note =

View on Pith arXiv 2019

[96] [100]

Fixed-Point Quantum Search with an Optimal Number of Queries , author =. prl , volume =. 2014 , doi =

View on Pith 2014

[97] [101]

Gilles Brassard and Peter H. Quantum Amplitude Amplification and Estimation , BOOKTITLE =. 2002 , doi =

View on Pith 2002

[98] [102]

Bernstein, Sergei , journal=. On a modification of

View on Pith

[99] [103]

High-Dimensional Statistics: A Non-Asymptotic Viewpoint , author=. 2019 , publisher=

View on Pith 2019

[100] [104]

Allcock, Jonathan and Hamoudi, Yassine and Joux, Antoine and Klingelh. Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming , booktitle =. 2022 , volume =

View on Pith 2022

[101] [105]

Xavier Bonnetain and Andr. Finding Many Collisions via Reusable Quantum Walks - Application to Lattice Sieving , booktitle =. 2023 , doi =

View on Pith 2023

[102] [106]

A log-depth in-place quantum Fourier transform that rarely needs ancillas , author=. arXiv preprint arXiv:2505.00701 , year=

View on Pith Pith review arXiv

[103] [107]

Approximate quantum Fourier transform in logarithmic depth on a line , author=. arXiv preprint arXiv:2504.20832 , year=

View on Pith Pith review arXiv

[104] [108]

Smooth input preparation for quantum and quantum-inspired machine learning , author=. Quantum Machine Intelligence , volume=. 2021 , publisher=

View on Pith 2021

[105] [109]

Stacey Jeffery , title =

View on Pith

[106] [110]

Ambainis, Andris , title =. Theory of Computing Systems , volume =. 2010 , publisher =

View on Pith 2010

[107] [111]

Alexandr Andoni and Negev Shekel Nosatzki , title =. Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science , pages =. 2020 , doi =

View on Pith 2020

[108] [112]

Mao, Xiao and Rubinstein, Aviad , title =. Proceedings of the 58th Annual ACM Symposium on Theory of Computing , pages =. 2026 , doi =

View on Pith 2026

[109] [113]

On the Complexity of k-SAT , journal =. 2001 , issn =. doi:https://doi.org/10.1006/jcss.2000.1727 , url =

View on Pith arXiv 2001

[110] [114]

Which Problems Have Strongly Exponential Complexity? , journal =. 2001 , issn =. doi:https://doi.org/10.1006/jcss.2001.1774 , url =

View on Pith arXiv 2001

[111] [115]

On the Fine-Grained Query Complexity of Symmetric Functions , author=. Information and Computation , volume=. 2025 , publisher=

View on Pith 2025

[112] [116]

Daniel R. Simon , title =. SIAM Journal on Computing , volume =. 1997 , publisher =

View on Pith 1997

[113] [117]

Fran. Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments , booktitle =. 2014 , doi =

View on Pith 2014

[114] [118]

Stacey Jeffery , title =. 2022 , note =

View on Pith 2022

[115] [119]

Andris Ambainis , title =. Theory of Computing Systems , volume =. 2010 , doi =

View on Pith 2010

[116] [120]

Buhrman, Harry and Patro, Subhasree and Speelman, Florian , title =. 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) , pages =. 2021 , volume =. doi:10.4230/LIPIcs.STACS.2021.19 , annote =

View on Pith doi:10.4230/lipics.stacs.2021.19 2021

[117] [121]

Arturs Backurs and Piotr Indyk , title =. Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC) , pages =. 2015 , doi =

View on Pith 2015

[118] [122]

Lov K. Grover , title =. Proceedings of the. 1996 , doi =

View on Pith 1996

[119] [123]

Fr. Search via Quantum Walk , journal =. 2011 , doi =

View on Pith 2011

[120] [124]

Herman Chernoff , title =. 1952 , journal =

View on Pith 1952

[121] [125]

Mitzenmacher, Michael and Upfal, Eli , title =. 2005 , publisher =

View on Pith 2005

[122] [126]

Peter H. Negative Weights Make Adversaries Stronger , booktitle =

View on Pith

[123] [127]

Howard Barnum and Michael Saks and Mario Szegedy , title =. Proceedings of the 18th IEEE Conference on Computational Complexity (CCC) , pages =. 2003 , doi =

View on Pith 2003

[124] [128]

Aleksandrs Belovs and Gilles Brassard and Peter H. Provably Secure Key Establishment Against Quantum Adversaries , booktitle =. 2018 , publisher =

View on Pith 2018

[125] [129]

Graeme Auld and Kritsana Neammanee , title =. Journal of Inequalities and Applications , volume =. 2024 , doi =

View on Pith 2024

[126] [130]

Darroch, J. N. , title =. The Annals of Mathematical Statistics , volume =. 1964 , doi =

View on Pith 1964

[127] [131]

Kuszmaul, William , title =. 2019 , booktitle =

View on Pith 2019