Pith. sign in

REVIEW 4 major objections 5 minor 45 references

Quantum solvability of noisy linear problems by divide-and-conquer strategy

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims a divide-and-conquer quantum algorithm solves bounded-error learning-with-errors with polynomial sample and time complexity while using an exponentially smaller superposition.

desk verdict A genuinely new divide-and-conquer idea for quantum LWE, but the main proof is undone by the authors' own error transformation, which shifts the recovered secret by A^{-1}η. read the letter →

arxiv 1908.06229 v8 pith:AXXLU7AY submitted 2019-08-17 quant-ph

Wooyeong Song , Youngrong Lim , Kabgyun Jeong , Yun-Seong Ji , Jinhyoung Lee , Jaewan Kim , M. S. Kim , Jeongho Bang This is my paper · ORCID
classification quant-ph
keywords learningwitherrorsquantumalgorithmdivideandconquerBVkernelboundederrormodelsamplecomplexityNISQGaussianelimination
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper claims that the learning-with-errors problem with bounded noise $|\eta|\le\xi=\alpha q$, $\alpha\ll 1$, and $q$ at most polynomial in $n$, can be solved by a quantum divide-and-conquer algorithm using $O(n\kappa\xi\log(n/\delta))$ quantum samples and $\mathrm{poly}(n,\log(n/\delta))$ time, with a superposition of only $O(q)$ states per coordinate instead of $O(q^n)$. The strategy splits the $n$-dimensional linear structure into one-dimensional subproblems by Gaussian elimination, prepares a small superposed quantum sample for each coordinate, and extracts the secret with a two-QFT Fourier kernel followed by a deterministic M-trial test. If correct, the result would put a quantum speedup for a cryptographically central problem within reach of near-term devices, exponentially reducing both sample-state size and QRAM cost relative to the earlier quantum approach. The claimed regime is $\xi=\mathrm{poly}(n)$ with $q$ polynomial in $n$ and $\kappa\xi\ll q$, where $\kappa=O(n^3)$ is the error amplification from elimination.

What carries the argument

The machinery is the one-coordinate Fourier kernel: applying $QFT_q$ to both the data and answer registers of the state $\frac{1}{\sqrt{|v_j|}}\sum_{a'_j\in v_j}|a'_j\rangle_D|a'_j s_j+\eta'_j\rangle_A$ produces a correlation through $k_j=-s_j k_\star$ plus a phase $\omega^{\eta'_j k_\star}$. The paper lower-bounds the probability of reading the correct correlation by $\gamma |v_j|\cos^2(2\pi\gamma)/(\xi' q)$; with $|v_j|=O(q)$ and $L=O(\xi'\ln(n/\delta))$ trials per coordinate, this supports the polynomial sample bound. The M-trial test is what turns a noisy single-shot candidate into a certified value, using deterministic samples to reject any $\tilde{s}_j$ that does not match within $\xi'$ on M independent trials.

What would settle it

Set $n=1$, choose $v_1=\mathbb{F}_q$ with $q$ prime and fixed nonzero noise $\eta$, and compute the exact success probability $P(\tilde{s}_1=s_1)=\frac{1}{q^2|v_1|}\sum_{k_\star\in\mathbb{F}_q}\left|\sum_{a\in v_1}\omega^{a\eta k_\star}\right|^2$. If this is $O(1/q)$ rather than the claimed lower bound $\gamma |v_1|\cos^2(2\pi\gamma)/(\xi' q)$, or if the accepted value is $s_1+\eta$ rather than $s_1$, the central polynomial-complexity claim is contradicted.

Watch

Extended reading notes

Core claim

The paper's central claim is that the learning-with-errors problem with $|\eta|\le\xi=\alpha q$, $\alpha\ll 1$, and $q$ at most polynomial in $n$, can be solved by a quantum divide-and-conquer algorithm in $O(n\kappa\xi\log(n/\delta))$ quantum samples and $\mathrm{poly}(n,\log(n/\delta))$ time, with success probability at least $1-\delta$. The method first uses Gaussian elimination to turn $n$-dimensional samples into $n$ independent coordinate pairs $(a'_j,\,a'_j s_j+\eta'_j)$, where the new noise is bounded by $\xi'=\kappa\xi$ with $\kappa=O(n^3)$; it then prepares a superposition over $O(q)$ values of $a'_j$ and runs a two-QFT Fourier kernel on that single coordinate. The measurement yields a candidate $\tilde{s}_j$, and an M-trial deterministic test accepts only candidates that agree with M fresh samples within $\xi'$, bounding the chance of accepting a wrong secret by $L(2\kappa\alpha)^M$. In the regime $\kappa\xi\ll q$, the superposition size, sample complexity, and time complexity are all polynomial, whereas the earlier quantum approach needed $O(q^n)$-sized superpositions.

Load-bearing premise

The algorithm's success bound assumes the transformed noise stays below a fixed small bound for every coefficient appearing in the quantum superposition, even though the noise formula makes that transformed noise proportional to the coefficient itself.

Editorial extensions

If this is right

  • For $\xi=\mathrm{poly}(n)$ and $q$ at most polynomial in $n$ with $\kappa\xi\ll q$, the algorithm learns the secret with probability at least $1-\delta$ using $O(n\kappa\xi\log(n/\delta))$ quantum samples and $\mathrm{poly}(n,\log(n/\delta))$ time.
  • The per-coordinate superposition size is $O(q)$ instead of $O(q^n)$, and the QRAM call cost drops from exponential to polynomial in the primitive model and to $O(\log q)$ operations in the bucket-brigade model.
  • Each coordinate is processed independently, so a single wrong candidate can be rejected by the M-trial test, and the overall failure probability can be pushed below $\delta$ by repeating each coordinate $L=C\xi'\ln(n/\delta)$ times.
  • In the noiseless limit the protocol identifies each coordinate with probability close to 1 using $O(q/(q-1)\,n)$ samples and $O(\mathrm{poly}(n))$ time, matching classical linear solving.

Reading between the lines

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

  • The error formula $\eta'_j=a'_j(A^{-1}\eta)_j$ implies the success bound in Eq. (7) depends on a uniform error bound that is not automatic when $v_j$ spans essentially all of $\mathbb{F}_q$; a quick numerical test for $n=1$ would reveal whether the central premise holds.
  • A natural repair direction is to restrict each superposition set to coefficients small enough that $|\eta'_j|\le\xi'$ still holds, but then $|v_j|$ shrinks and the claimed sample-complexity gain must be recomputed; the paper does not analyze this trade-off.
  • The M-test as written certifies consistency with transformed samples; if those samples are consistent with a shifted secret, the test cannot distinguish the shift, so the stated failure bound $L(2\kappa\alpha)^M$ applies only when the uniform error bound is available.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The manuscript proposes a divide-and-conquer quantum algorithm for the learning-with-errors (LWE) problem with bounded error |η| ≤ ξ = αq. It uses Gaussian elimination to create n reduced single-coordinate samples, superposes over data values a'_j in a subset v_j ⊆ F_q, applies a Bernstein-Vazirani QFT kernel, and verifies candidates with an M-trial test. The paper claims polynomial quantum-sample complexity O(nκξ log(n/δ)) and poly(n) time for q polynomial in n and κ = O(n^3), with superposition size O(q) instead of O(q^n), and argues this gives a tangible or NISQ-compatible quantum speedup.

Significance. If the central claim were sound, the contribution would be significant: it would improve the superposition-size and QRAM-call overheads relative to the earlier quantum LWE algorithm of Grilo et al., and it would give one of the few concrete quantum speedup proposals tailored to near-term devices. The paper also contains a useful comparison with classical BKW-type algorithms and an unusually honest statement of limitations, including the need for O(n^2 q) classical samples and the restriction to polynomial q. However, the central noise analysis is invalid: the reduced noise is not uniformly bounded over the superposition, and Gaussian elimination deterministically shifts the secret that the algorithm learns. The stated polynomial complexity is therefore unsupported.

major comments (4)
  1. [Supplement Eq. (S13); main Eq. (2)] The supplement defines η'_j = a'_j (A^{-1}η)_j in Eq. (S13), and the main text's Eq. (2) uses this quantity in the state |ψ_j>. Consequently each reduced sample is exactly (a'_j, a'_j(s_j+c_j)) with c_j=(A^{-1}η)_j; this is a noiseless sample for the shifted secret s_j+c_j, not a bounded-error sample for s_j. The assertion in the paragraph after Eq. (2) that |η'_j| ≤ ξ' = κξ uniformly for all a'_j ∈ v_j is therefore false whenever |v_j| = O(q) and c_j ≠ 0, because v_j then contains elements of size Θ(q). For random bounded η and invertible A, c_j ≠ 0 with probability 1 - O(ξ/q), so the uniform bound is not a minor technicality.
  2. [Eqs. (5)-(7) and Supplement Eqs. (S17)-(S20)] The derivation of P(s̃_j = s_j) uses Re(ω^{η'_j k*}) ≥ cos(2πγη'_j/ξ') ≥ cos(2πγ) with k* ≤ γq/ξ', which requires |η'_j| ≤ ξ' for every a'_j ∈ v_j. As shown above, |η'_j| can be Θ(q)|c_j|, so the phase condition fails for large a'_j and Eq. (7) is not a valid lower bound. The probability estimated in Eq. (7) is at best the probability of measuring the shifted secret s_j+c_j; it does not quantify success for s_j. In particular, choosing v_j with small |a'_j| to restore boundedness would give |v_j| = O(ξ'), not O(q), which destroys the polynomial bound and contradicts the paper's own requirement |v_j| = O(q).
  3. [M-trial test, T.1-T.2; Eq. (3)] The deterministic test samples in T.1 are constructed by the same Gaussian-elimination procedure, so their labels are t_j(s_j+c_j) rather than t_j s_j + η'_j with bounded η'_j. For the shifted candidate s̃_j = s_j+c_j, ∆_j = 0 and the test accepts the wrong value; for the true s_j, ∆_j = |t_j c_j| can exceed ξ', so the true value can be rejected. Thus the M-test does not certify the original secret, and the failure-probability bound in Eq. (3) does not apply to the event described.
  4. [Analysis, Eqs. (8)-(10); sample complexity] Since Eqs. (3) and (7) are the only ingredients for the overall success probability Prob(i) ≥ 1 - δ and for the quantum-sample bound O(nκξ log(n/δ)), the claimed polynomial sample and time complexities are unsupported. The structural reason is the deterministic shift s → s + A^{-1}η introduced by Gaussian elimination; this is not an error that can be bounded away by a better concentration estimate within the algorithm's current design.
minor comments (5)
  1. [Title and abstract] The title of this arXiv version ('Tangible Quantum Speedup in Learning-With-Errors Problem') and the abstract in the submission ('Quantum solvability of noisy linear problems...') describe different claims; the title and abstract should be aligned.
  2. [Eq. (2)] In Eq. (2), 'fo' should be 'for' in the sentence introducing the less-superposed quantum sample.
  3. [References] Reference numbering is inconsistent: the main text's reference [1] (Arute et al.) and the supplemental reference [1] (Giovannetti et al.) duplicate the label, and the supplementary bibliography contains its own numbered entries [2]-[7] that do not belong to the main numbering.
  4. [Eq. (3)] The sentence after Eq. (3) stating that 'O(κα) does not decay faster than O(q^{-1}) because α ≪ κ^{-1}' is confusing and appears to state the opposite of the intended relation; please rephrase with explicit inequalities.
  5. [Eq. (7) and Acknowledgments] Eq. (7) introduces a free parameter γ ∈ [0,1/4) and the cutoff '⌊γq/ξ'⌉' without defining the rounding; state the precise summation range. In the Acknowledgments, 'Marcin Paw/suppress lowski' appears to be a corrupted name.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the central divide-and-conquer derivation is self-contained; the paper's main weakness is a mathematical error in the error bound, not a circular reduction.

full rationale

The paper's derivation is self-contained and not circular. The divide-and-conquer samples in Eq. (2) are constructed by Gaussian elimination on the given classical LWE samples, and the Bernstein-Vazirani subroutine is used to estimate each s_j from these samples; the success bound in Eq. (7) is derived from the Fourier amplitudes, and the sample complexity O(nκξ log(n/δ)) follows from that bound together with the repetition count L in Eq. (9). None of these quantities is fitted to the target or renamed from the input: the reduced error η'_j = a'_j(A^{-1}η)_j is the paper's own definition in Eq. (S13), and the analysis assumes, rather than derives, its uniform boundedness. The only shared-authorship citation, Ref. [7] in the supplementary QRAM discussion, supports a benign storage assumption about deterministic input states and is not load-bearing for the claimed speedup. There is no imported uniqueness theorem and no ansatz smuggled in via self-citation. The serious weakness is a mathematical gap: Eq. (S13) defines η'_j = a'_j(A^{-1}η)_j, while Eqs. (7)/(S20) require |η'_j| ≤ ξ' uniformly for all a'_j in v_j with |v_j| = O(q); for a nonzero (A^{-1}η)_j, this uniform bound fails when a'_j ranges over a constant fraction of F_q, so the polynomial success probability is not established. This is an error in the derivation, not a circular reduction of the conclusion to the assumptions. Accordingly, the circularity score is 0.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical entities. The central load-bearing assumption is the uniform noise bound after Gaussian elimination, which is an ad hoc assumption contradicted by the paper's own error scaling equation. The other axioms are standard mathematical tools and the stated LWE error model.

free parameters (1)
  • γ = unspecified, in [0, 1/4)
    Chosen by hand to truncate the k⋆ sum and obtain the cosine lower bound in Eq. (7). It affects the constant factor in the success probability but not the asymptotic claim.
assumptions (4)
  • ad hoc to paper The error after Gaussian elimination is bounded as |η'_j| ≤ κξ with κ = O(n^3), uniformly for all a'_j in v_j.
    This is the load-bearing assumption that the paper's own Eq. (S13) contradicts, since η'_j = a'_j (A^{-1}η)_j scales with a'_j.
  • domain assumption The error distribution χ is supported on [-ξ, ξ] with ξ = αq and α ≪ 1, and q is of order higher than O(poly(n)).
    Restricts the LWE instances to low-noise, large-field settings; the authors acknowledge this in the discussion.
  • domain assumption The quantum sample state |ψ_j> can be prepared with |v_j| = O(q) elements using classical Gaussian elimination with O(n^3) summations per pair.
    Assumes the classical preprocessing does not destroy the quantum advantage and that the resulting superposed samples are faultlessly prepared.
  • standard math Standard properties of QFT over F_q and the delta function identity δ_{k,-s k⋆} = (1/q) Σ_a ω^{a(k + s k⋆)}.
    Used in the noiseless analysis and the calculation of Eq. (4).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum solvability of noisy linear problems by divide-and-conquer strategy." pith.science (2026). https://pith.science/paper/AXXLU7AY

@misc{pith2026190806229,
  author       = {Pith},
  title        = {Pith review of: Quantum solvability of noisy linear problems by divide-and-conquer strategy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AXXLU7AY}},
  note         = {Machine review of arXiv:1908.06229}
}
abstract

Noisy linear problems have been studied in various science and engineering disciplines. A class of "hard" noisy linear problems can be formulated as follows: Given a matrix $\hat{A}$ and a vector $\mathbf{b}$ constructed using a finite set of samples, a hidden vector or structure involved in $\mathbf{b}$ is obtained by solving a noise-corrupted linear equation $\hat{A}\mathbf{x} \approx \mathbf{b} + \boldsymbol\eta$, where $\boldsymbol\eta$ is a noise vector that cannot be identified. For solving such a noisy linear problem, we consider a quantum algorithm based on a divide-and-conquer strategy, wherein a large core process is divided into smaller subprocesses. The algorithm appropriately reduces both the computational complexities and size of a quantum sample. More specifically, if a quantum computer can access a particular reduced form of the quantum samples, polynomial quantum-sample and time complexities are achieved in the main computation. The size of a quantum sample and its executing system can be reduced, e.g., from exponential to sub-exponential with respect to the problem length, which is better than other results we are aware. We analyse the noise model conditions for such a quantum advantage, and show when the divide-and-conquer strategy can be beneficial for quantum noisy linear problems.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

45 extracted references · 32 canonical work pages

  1. [1]

    Arute, K

    F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al., Nature 574, 505 (2019)

    2019

  2. [2]

    Preskill, Quantum 2, 79 (2018)

    J. Preskill, Quantum 2, 79 (2018)

    2018

  3. [3]

    Boixo, S

    S. Boixo, S. V. Isakov, V. N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven, Nature Physics 14, 595 (2018)

    2018

  4. [4]

    Bouland, B

    A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, Nature Physics 15, 159 (2019)

    work page 2019

  5. [5]

    Peruzzo, J

    A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’brien, Nature Communications 5, 4213 (2014)

    work page 2014

  6. [6]

    Universal Variational Quantum Computation

    J. Biamonte, arXiv preprint arXiv:1903.04500 (2019)

    work page Pith review arXiv 2019

  7. [7]

    X. Xu, J. Sun, S. Endo, Y. Li, S. C. Benjamin, and X. Yuan, arXiv preprint arXiv:1909.03898 (2019)

    arXiv 2019

  8. [8]

    Bravo-Prieto, R

    C. Bravo-Prieto, R. LaRose, M. Cerezo, Y. Subasi, L. Cin- cio, and P. J. Coles, arXiv preprint arXiv:1909.05820 (2019)

    arXiv 2019

Show all 45 references
  1. [9]

    Havl ´ ıˇ cek, A

    V. Havl ´ ıˇ cek, A. D. C´ orcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta, Nature 567, 209 (2019)

    2019

  2. [10]

    J. Yang, A. J. Awan, and G. Vall-Llosera, arXiv preprint 5 arXiv:1909.11988 (2019)

    2019 arXiv

  3. [11]

    Anschuetz, J

    E. Anschuetz, J. Olson, A. Aspuru-Guzik, and Y. Cao, in International Workshop on Quantum Technology and Optimization Problems (Springer, 2019), pp. 74–85

    2019

  4. [12]

    Zhang and V

    K. Zhang and V. E. Korepin, arXiv preprint arXiv:1908.04171 (2019)

    2019 arXiv

  5. [13]

    Regev, Journal of the ACM (JACM) 56, 34 (2009)

    O. Regev, Journal of the ACM (JACM) 56, 34 (2009)

    2009

  6. [14]

    Regev, in Proceedings of the 2010 IEEE 25th Annual Conference on Computational Complexity (2010), CCC ’10, pp

    O. Regev, in Proceedings of the 2010 IEEE 25th Annual Conference on Computational Complexity (2010), CCC ’10, pp. 191–204, ISBN 978-0-7695-4060-3

    2010

  7. [15]

    A. B. Grilo, I. Kerenidis, and T. Zijlstra, Physical Rev iew A 99, 032314 (2019)

    2019

  8. [16]

    A. Blum, A. Kalai, and H. Wasserman, Journal of the ACM (JACM) 50, 506 (2003)

    2003

  9. [17]

    Micciancio, Encyclopedia of Cryptography and Secu- rity pp

    D. Micciancio, Encyclopedia of Cryptography and Secu- rity pp. 713–715 (2011)

    2011

  10. [18]

    Brakerski, A

    Z. Brakerski, A. Langlois, C. Peikert, O. Regev, and D. Stehl´ e, in Proceedings of the forty-fifth annual ACM symposium on Theory of computing (ACM, 2013), pp. 575–584

    2013

  11. [19]

    M. R. Albrecht, R. Player, and S. Scott, Journal of Math- ematical Cryptology 9, 169 (2015)

    2015

  12. [20]

    Giovannetti, S

    V. Giovannetti, S. Lloyd, and L. Maccone, Physical Re- view Letters 100, 160501 (2008)

    2008

  13. [21]

    Giovannetti, S

    V. Giovannetti, S. Lloyd, and L. Maccone, Physical Re- view A 78, 052310 (2008)

    2008

  14. [22]

    Aaronson, Nature Physics 11, 291 (2015)

    S. Aaronson, Nature Physics 11, 291 (2015)

    2015

  15. [23]

    Brakerski and V

    Z. Brakerski and V. Vaikuntanathan, SIAM Journal on Computing 43, 831 (2014)

    2014

  16. [24]

    Bernstein and U

    E. Bernstein and U. Vazirani, SIAM Journal on Comput- ing 26, 1411 (1997)

    1997

  17. [25]

    Arunachalam, V

    S. Arunachalam, V. Gheorghiu, T. Jochym-O’Connor, M. Mosca, and P. V. Srinivasan, New Journal of Physics 17, 123010 (2015)

    2015

  18. [26]

    Lyubashevsky, in Approximation, randomization and combinatorial optimization

    V. Lyubashevsky, in Approximation, randomization and combinatorial optimization. Algorithms and techniques (Springer, 2005), pp. 378–389

    2005

  19. [27]

    Arora and R

    S. Arora and R. Ge, in International Colloquium on Au- tomata, Languages, and Programming (Springer, 2011), pp. 403–415

    2011

  20. [28]

    L. N. Trefethen and D. Bau III, Numerical linear algebra, vol. 50 (SIAM, 1997)

    1997

  21. [29]

    It is assumed that the equations ai · s = bi are linearly independent and ˆA− 1 exists

    Here, A− 1 is the modular inverse matrix. It is assumed that the equations ai · s = bi are linearly independent and ˆA− 1 exists. The (classical) cost for finding ˆA− 1 is at most O(n3) [28]

  22. [30]

    However, in this work, we focus on the L WE by considering q > 2

    In the case of the learning parity with noise (LPN) prob- lem, the error model is simplified such that ηa is 0 or 1 with probabilities 1 − p or p, respectively. However, in this work, we focus on the L WE by considering q > 2

  23. [31]

    Here, the condition L ≤ q is attributable to the fact that the possible number of ˜sj is q

  24. [32]

    Thus, the probability of identifying sj is 1 − 1 q . There- fore, only n repetitions of the above process allow finding the solution s = s0s1 · · · sn− 1 without any testing process, where the number of required sample states is O( q q− 1 n) and the algorithm takes O(poly(n)) t...

  25. [33]

    Nevertheless, we indicate that the divide-and-conque r strategy is not always successful. In fact, in the classical L WE setting, it does not bring any improvement owing to exponential decrease of the success probability in sam- pling a specifically structured data, as noted by...

  26. [34]

    if a quantum adversary has access to a particular superposition of quantum states

    This problem is also applied to the original algorithm o f Grilo et al . [15]. In their study, the significant assump- tion “ ...if a quantum adversary has access to a particular superposition of quantum states... ” was applied

  27. [35]

    Thus, total O(n2 × q) classical samples are required to complete the algorithm

    We need O(n × q) original samples for a j-th trial quan- tum sample and we should repeat this n times. Thus, total O(n2 × q) classical samples are required to complete the algorithm

  28. [36]

    This specific condition does not alter the L WE hardness at all; thus, solving on a classical computer remains hard and our results are sufficiently meaningful. 6 S1. QRAM AND QUANTUM SAMPLE Random-access memory (RAM) is used to interrogate a database in computation. Specifically,...

  29. [37]

    Note here that the factor γ ∈ [0, 1

    and k⋆ ≤ γq ξ . Note here that the factor γ ∈ [0, 1

  30. [38]

    (S18), applying the periodic boundary condition, and it leads to ∑ k⋆∈Fq → ∑ k⋆≤⌊ γq ξ ⌉ withk⋆ ≤ γq ξ

    is adopted for the calculation of Re ( ωη′ j k⋆ ) in Eq. (S18), applying the periodic boundary condition, and it leads to ∑ k⋆∈Fq → ∑ k⋆≤⌊ γq ξ ⌉ withk⋆ ≤ γq ξ . Then, we can attain the lower bound of P (˜sj =sj) (as in Eq. (7) of the main manuscript) such that P (˜sj =sj) ≥ 1...

  31. [39]

    Giovannetti, S

    V. Giovannetti, S. Lloyd, and L. Maccone, Physical revie w letters 100, 160501 (2008)

    2008

  32. [40]

    A. W. Harrow, A. Hassidim, and S. Lloyd, Physical review l etters 103, 150502 (2009)

    2009

  33. [41]

    Kerenidis and A

    I. Kerenidis and A. Prakash, arXiv preprint arXiv:1603. 08675 (2016)

    2016

  34. [42]

    Rebentrost, M

    P. Rebentrost, M. Mohseni, and S. Lloyd, Physical review letters 113, 130503 (2014)

    2014

  35. [43]

    Lloyd, M

    S. Lloyd, M. Mohseni, and P. Rebentrost, Nature Physics 10, 631 (2014)

    2014

  36. [44]

    Biamonte, P

    J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wi ebe, and S. Lloyd, Nature 549, 195 (2017)

    2017

  37. [45]

    J. Bang, A. Dutta, S.-W. Lee, and J. Kim, Physical Review A 99, 012326 (2019)

    2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.