Pith. sign in

REVIEW 3 major objections 4 minor 71 references

Quantum Wave Atom Transforms

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read This paper constructs the first efficient quantum circuit for a wave atom transform with parabolic scaling, achieving $O(L^2)$ gate complexity for vectors of dimension $2^L$.

desk verdict Serious construction with a real but patchable gap: the O(L^2) circuit for wave-atom-admissible trees looks right, but the advertised coverage of parabolic scaling trees is not proven. read the letter →

arxiv 2507.10739 v3 pith:Z2K5Y52Z submitted 2025-07-14 quant-ph cs.NAmath.NA

Marianna Podzorova , Yi-Kai Liu This is my paper
classification quant-phcs.NAmath.NA MSC 81P6842C4065T60
keywords quantumwaveatomtransformparabolicscalingpackettreewaveletblendingmatrixfrequencyencodinggatecomplexityequation
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 tries to establish that wave atom transforms—wavelet packet transforms whose basis functions obey a parabolic scaling law (wavelength proportional to diameter squared)—can be implemented on a quantum computer with polylogarithmic gate cost. For a transform acting on a vector of dimension $N=2^L$, the constructed circuit uses $O(L^2)$ one- and two-qubit gates, compared with the classical cost $O(N\log N)$. The construction covers a large family of wave packet trees, including the monotonic trees that contain parabolic-scaling trees as a special case. If the construction holds, it gives the first efficient quantum implementation of wave atoms and a concrete step toward quantum algorithms for wave equations that could run exponentially faster than classical discretization-based solvers, though the paper leaves the sparse-approximation step for wave propagators as an open technical problem.

What carries the argument

The key machinery is the tree encoding together with a three-factor matrix decomposition. A wave packet tree is represented by helper functions $h_j(p)$ that tell whether the encoded index $p=m2^j+n$ lies at or above level $j$; for monotonic trees these are comparisons against leftmost-leaf positions and cost $O(L^2)$ gates. The wave atom transform matrix is factored as $C_A=F_A R^\dagger G_A R$: $F_A$ is a block-diagonal Fourier-type transform that acts inside each tree node's subspace, $R$ is a permutation that moves overlapping frequency pairs next to each other, and $G_A$ is a block-diagonal blending matrix whose $2\times 2$ blocks use the wave-atom profile $g$ to redistribute amplitude between overlapping wave packets. Conditions (11)--(12) on $g$ make every block unitary, and the specific $g$ in Eq. (67) is chosen so that each block is a linear Pauli rotation implementable with comparators and controlled rotations.

What would settle it

Check a parabolic-scaling tree from Eq. (20): list its leaf levels from left to right. If any neighboring pair has $|j_i-j_{i+1}|>1$ or violates the parity conditions of Definition 5.1, then Corollary 5.6 does not apply to that tree. On the numerical side, compute the Gram matrix of the discrete wave atoms $\tilde\psi^j_{m,n}$ at integer frequencies for such a tree: if Eq. (38) fails for some neighboring leaves, the transform matrix $C_A$ is not unitary and the factorization cannot be exact.

Watch

Extended reading notes

Core claim

The central claim is that the 1D wave atom transform, defined by a wave-atom admissible tree and a mother wave atom built from the profile function $g$, is a unitary that can be decomposed as $C_A = F_A R^\dagger G_A R$, where $F_A$ is a Fourier transform adapted to the tree structure, $R$ is a permutation that pairs up overlapping frequency components, and $G_A$ is a block-diagonal blending matrix. Each of these factors is shown to be implementable by $O(L^2)$ gates when the tree is monotonic and represented by the leftmost leaf index at each level, and when $g$ is the specific cosine-bump function in Eq. (67). The upshot is Corollary 5.6: for a monotonic wave atom admissible tree on $O(2^L)$ points, the quantum wave atom transform has gate complexity $O(L^2)$. The paper frames this as the first efficient quantum implementation of a wave atom transform and a positive answer to the feasibility question for parabolic-scaling wavelet packet transforms.

Load-bearing premise

The construction assumes that every parabolic-scaling tree used in wave atom applications is a wave atom admissible tree in the sense of Definition 5.1; the paper proves that parabolic scaling implies monotonicity, but does not show that the level-adjacency condition $|j_i-j_{i+1}|\le 1$ and the parity rules follow from Eq. (20).

Editorial extensions

If this is right

  • A unitary approximation to a wave atom transform on $N=2^L$ points can be applied with $O(L^2)$ gates, so the cost per point is polylogarithmic rather than the classical $O(N\log N)$.
  • The same encoding and decoding framework yields an $O(L^2)$-gate quantum Shannon wavelet transform for monotonic trees, extending previous quantum wavelet results to a larger class of tree structures.
  • With the Solovay-Kitaev theorem, approximating the arbitrary one- and two-qubit gates by a fixed gate set preserves the $O(L^2)$ scaling up to a polylogarithmic factor in $L$ and $1/\epsilon$.
  • If the sparse wave-propagator approximations used classically can be made to work in operator norm, this becomes a route to exponentially faster quantum algorithms for wave equations.

Reading between the lines

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

  • The paper treats parabolic-scaling trees as a special case via monotonicity, but the inclusion of parabolic-scaling trees in Definition 5.1 is not proved; verifying or disproving that inclusion is a direct test of whether the advertised corollary covers the wave atoms used in classical wave-equation solvers.
  • The $O(L^2)$ count assumes arbitrary one- and two-qubit gates and a fully connected qubit topology; on a nearest-neighbor architecture the permutation and controlled rotations would likely acquire an additional layout-dependent factor.
  • The blending technique is not tied to the particular tree or profile function; the same $C_A=F_A R^\dagger G_A R$ decomposition could be implemented for other admissible trees and other profiles $g$ as long as each $2\times 2$ block remains unitary, potentially transferring the method to curvelet-like or higher-dimensional constructions.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper constructs quantum circuits for wavelet packet transforms organized by binary trees, with the stated goal of implementing wave atom transforms with parabolic scaling. It introduces frequency-encoding and retaining-decoding circuits, then builds a quantum Shannon wavelet transform for monotonic trees (Theorem 4.1). For wave atoms it proves the algebraic decomposition C_A = F_A R^dagger G_A R (Theorem 5.3), supplies circuit implementations for F_A, G_A, and R, and derives an O(L^2) gate complexity for wave atom admissible trees (Theorem 5.5) and for monotonic trees with an explicit function g (Corollary 5.6). The paper also discusses potential applications to quantum wave-equation solvers.

Significance. If the main claim is established, the paper is a substantial advance: it gives the first quantum circuit family implementing a wave atom transform with gate count polylogarithmic in N = 2^L, and it does so with a detailed, apparently checkable algebraic decomposition and explicit algorithms for each component. The separation of tree-index arithmetic from the g-dependent blending is elegant, and the concrete g in Eq. (67) is simple enough to verify the orthogonality relations. The paper is honest about the Solovay-Kitaev overhead and about the heuristic status of the wave-equation applications. The principal weakness is that the advertised coverage of parabolic scaling trees is not established; this affects the paper's central claim and requires a substantive revision.

major comments (3)
  1. [§2.3, Proposition 2.1] The statement that every admissible tree satisfying the parabolic scaling relation (20) is monotonic is false under the natural leaf-dependent reading of m proportional to 2^j and vacuous under a global-constant reading. Consider the admissible tree with root W^4_0 and leaves W^3_0, W^2_2, W^2_3, obtained by splitting W^4_0 into W^3_0 and W^3_1, and then splitting only W^3_1. Its leaves satisfy m/2^j in {0, 1/2, 3/4}, so each leaf has its own proportionality constant, but the j-sequence is 3, 2, 2 and the tree is not monotonic. If instead the constant is required to be the same for all leaves, no nontrivial admissible tree satisfies (20), because Proposition 2.2(1) forces the leftmost leaf to have m = 0, which forces the common constant to be 0. The proof's intermediate claim 'Since T is admissible, we have m <= m''' is not generally valid for arbitrary pairs of leaves and needs a justification that uses the leaf ordering.
  2. [§5.2, Definition 5.1 and Corollary 5.6] The paper's final claim that the O(L^2) result applies to parabolic scaling trees is not supported by the stated hypotheses. A monotonic, parabolic (in the leaf-dependent sense) tree need not be wave atom admissible. For L = 5, split every node W^j_m with j >= 2 and m < 2^j. The leaves are W^1_0 through W^1_7 followed by W^2_4 through W^2_7; the tree is admissible and monotonic, and all leaf ratios m/2^j are bounded (between 0 and 3.5), but the adjacent pair W^1_7, W^2_4 has j_{i+1} = j_i + 1 with m_i = 7 odd and m_{i+1} = 4 even, violating condition 2 of Definition 5.1. Correspondingly, mu_1(1,7) = 0 while mu_0(2,4) = 1, so condition (38) fails. Thus Corollary 5.6 does not apply to this parabolic scaling tree. The paper must either prove that the specific class of trees used in classical wave atom applications is contained in Definition 5.1, or state and prove a sufficient condition for parabolic scaling trees to be wave atom admissible.
  3. [§5.3, Theorem 5.3] The decomposition C_A = F_A R^dagger G_A R is the core of the paper, and the proof is detailed. However, the argument relies on the equality (56) for neighboring leaf nodes when j' = j +/- 1, and this equality uses the parity conditions of Definition 5.1. Since Definition 5.1 is introduced as the class satisfying Eq. (38), the equivalence between the parity conditions and Eq. (38) should be proved explicitly rather than left as 'straightforward to see' (Section 5.2). This is not a question of correctness but a missing derivation at a load-bearing point; a short proof would also clarify why level differences larger than 1 are excluded.
minor comments (4)
  1. [§2.2, Eq. (13)] The intervals A1 and A2 are written as closed intervals, while the support of g is stated to be the open interval (-7pi/6, 5pi/6). Please reconcile the endpoint convention.
  2. [§3.2.1, monotonic-tree paragraph] The definition of m*_j for levels with no leaf nodes is a little hard to parse; a small example or a pseudocode sketch would help the reader understand the encoding assumption used in Theorem 4.1 and Corollary 5.6.
  3. [§5.6.1, after Eq. (73)] The assertion that the permutations dot_rho^j_m pairwise commute is stated without proof; because adjacent leaf blocks meet at shared boundaries, a short argument using Proposition 2.2 would make the O(L^2) implementation of R more convincing.
  4. [§5.3, Lemma 5.2] In the last displayed equation of Lemma 5.2, the notation G^A_{rho((m+1)2^j - s, c} is missing a comma before c and is difficult to parse; please fix the typesetting.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the quantum wave atom transform is derived self-contained from the wave atom definitions, external orthonormality results, and standard QFT/arithmetic primitives.

full rationale

The central derivation chain is self-contained. The paper defines the wave atom transform via the wave atom functions of Villemoes and Demanet-Ying (Eqs. 9–10, cited to [4,5]), defines wave atom admissible trees (Definition 5.1), and then proves, in Theorem 5.3, the operator identity C_A = F_A R^dagger G_A R, with the lemmas supplying the detailed algebraic verification. Unitarity is shown from properties (11)–(12) of g, and gate complexity O(L^2) is obtained by explicit circuits for the QFT, the retaining decoding circuit, the linear Pauli rotations for G_A, and the permutation R. None of these steps fits a parameter to the quantity being predicted, nor does the derivation rename a known result: the product decomposition is a theorem proved from the matrix definitions. The only self-citations (Liu [34,35]) occur in speculative application remarks and do not support the main theorem. The paper's final claim that parabolic scaling trees are covered as a special case depends on Section 2.3, which only proves that parabolic scaling implies monotonicity, and does not show that such trees satisfy the extra level-difference and parity conditions of Definition 5.1. This is a correctness gap about hypothesis coverage, not a circularity: the result is not assumed in its inputs and the gap can be fixed by an independent inclusion proof. Accordingly, no specific circular step can be exhibited, and the appropriate finding is no significant circularity.

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

The central claim depends on the standard wave atom basis of Villemoes and Demanet-Ying, an unproved sufficiency of the wave atom admissible tree conditions for unitarity, and a hand-chosen g profile with specifically chosen coefficients. The tree representation h_j is provided for monotonic trees, so it is not pulled from thin air. No invented physical entities appear.

free parameters (1)
  • g profile slopes and offsets (3/8, 3/4, -pi/16, -pi/8) = 3/8, 3/4, -pi/16, -pi/8, support endpoints -7pi/6, pi/6, 5pi/6
    Hand-chosen constants in Eq (67) that satisfy orthogonality identities (11)-(12) and make blending rotations exactly expressible as linear Pauli rotations in Algorithm 6. They are not data-fitted but are introduced ad hoc to make the efficient implementation work.
assumptions (4)
  • standard math Villemoes wave atoms defined by Eqs (9)-(10) form an orthonormal basis when g satisfies Eqs (11)-(12).
    Imported from cited prior work [4,5]. The paper's support characterization in Proposition 5.1 and the decomposition C_A=F_A R^dagger G_A R rely on this basis.
  • domain assumption A wave atom admissible tree (Definition 5.1) is sufficient for the discrete wave atom transform C_A to be unitary.
    The paper derives Definition 5.1 from condition (38) via Proposition 5.2, but the proof is sketched and the boundary modifications in Eq (39) are asserted to restore unitarity. The central complexity theorem depends on this.
  • domain assumption Arbitrary 1- and 2-qubit gates are available exactly, with Solovay-Kitaev approximation by a finite gate set.
    Stated in Section 2.1; this justifies counting gates without the O(1/epsilon) factor.
  • ad hoc to paper The function g in Eq (67) satisfies Eqs (11)-(12) and is compactly supported.
    This specific g is introduced in Section 5.5.1 to make G_A efficiently implementable. It is verifiable by substitution, but the paper gives no explicit proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum Wave Atom Transforms." pith.science (2026). https://pith.science/paper/Z2K5Y52Z

@misc{pith2026250710739,
  author       = {Pith},
  title        = {Pith review of: Quantum Wave Atom Transforms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Z2K5Y52Z}},
  note         = {Machine review of arXiv:2507.10739}
}
read the original abstract

This paper constructs the first efficient implementation of a quantum wavelet packet transform with a "parabolic scaling" tree structure, sometimes called a quantum wave atom transform. Classically, wave atom transforms are used to construct sparse representations of differential operators, which enable fast classical algorithms for solving wave equations. Compared to previous work on quantum wavelet transforms, our quantum algorithm can implement a larger class of wavelet and wave atom transforms, by using an efficient representation for a larger class of possible tree structures. Our quantum implementation has O(poly(n)) gate complexity for applying a transform of dimension 2^n, while classical implementations use O(n 2^n) floating point operations. This is potentially useful for designing quantum algorithms for solving wave equations that achieve an exponential speedup over classical algorithms.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

71 extracted references · 57 canonical work pages

  1. [1]

    Proceedings of the Royal Society of London

    Jozsa, R.: Quantum algorithms and the fourier transform. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences454(1969), 323–337 (1998) https://doi.org/10.1098/rspa.1998.0163

    arXiv 1969

  2. [2]

    Reviews of Modern Physics 82(1), 1–52 (2010)

    Childs, A.M., Van Dam, W.: Quantum algorithms for algebraic problems. Reviews of Modern Physics 82(1), 1–52 (2010)

    work page 2010

  3. [3]

    PhD thesis (2006)

    Demanet, L.: Curvelets, wave atoms, and wave equations. PhD thesis (2006). https://doi.org/10. 7907/1TEF-RQ51 . https://resolver.caltech.edu/CaltechETD:etd-05262006-133555

    work page 2006

  4. [4]

    Applied and Computational Harmonic Analysis23(3), 368–387 (2007) https://doi.org/10.1016/j.acha.2007.03.003

    Demanet, L., Ying, L.: Wave atoms and sparsity of oscillatory patterns. Applied and Computational Harmonic Analysis23(3), 368–387 (2007) https://doi.org/10.1016/j.acha.2007.03.003

    work page doi:10.1016/j.acha.2007.03.003 2007

  5. [5]

    Comptes Rendus Mathematique335, 793–796 (2002)

    Villemoes, L.F.: Wavelet packets with uniform time-frequency localization. Comptes Rendus Mathematique335, 793–796 (2002)

    work page 2002

  6. [6]

    Demanet, L., Ying, L.: Wave atoms and time upscaling of wave equations. Numer. Math. (Heidelb.) 113(1), 1–71 (2009)

    work page 2009

  7. [7]

    Applied and Computational Harmonic Analysis32, 155–168 (2012) https://doi.org/10.1016/j.acha.2011.03.006

    Demanet, L., L´ etourneau, P.-D., Boumal, N., Calandra, H., Chiu, J., Snelson, S.: Matrix probing: A randomized preconditioner for the wave-equation hessian. Applied and Computational Harmonic Analysis32, 155–168 (2012) https://doi.org/10.1016/j.acha.2011.03.006

    work page doi:10.1016/j.acha.2011.03.006 2012

  8. [8]

    https://arxiv.org/abs/quant-ph/9702028

    Hoyer, P.: Efficient Quantum Transforms (1997). https://arxiv.org/abs/quant-ph/9702028

    arXiv 1997

Show all 71 references
  1. [9]

    https://arxiv.org/abs/quant-ph/9809004

    Fijany, A., Williams, C.P.: Quantum Wavelet Transforms: Fast Algorithms and Complete Circuits (1998). https://arxiv.org/abs/quant-ph/9809004

    1998 arXiv

  2. [10]

    In: Unser, M.A., Aldroubi, A., Laine, A.F

    Klappenecker, A.: Wavelets and wavelet packets on quantum computers. In: Unser, M.A., Aldroubi, A., Laine, A.F. (eds.) Wavelet Applications in Signal and Image Processing VII. SPIE, Bellingham, W A (1999)

    1999

  3. [11]

    Quantum Information & Computation9, 414–422 (2009)

    Arg¨ uello, F.: Quantum wavelet transforms of any order. Quantum Information & Computation9, 414–422 (2009)

    2009

  4. [12]

    Li, H.-S., Fan, P., Xia, H.-Y., Song, S.: Quantum multi-level wavelet transforms. Inf. Sci. (Ny)504, 113–135 (2019)

    2019

  5. [13]

    Zhang, Z., Kon, M.A.: Wavelet matrix operations and quantum transforms. Appl. Math. Comput. 428(127179), 127179 (2022)

    2022

  6. [14]

    Quantum Science and Technology9(3), 035010 (2024) https://doi.org/10.1088/2058-9565/ ad3d7f

    Bagherimehrab, M., Aspuru-Guzik, A.: Efficient quantum algorithm for all quantum wavelet trans- forms. Quantum Science and Technology9(3), 035010 (2024) https://doi.org/10.1088/2058-9565/ ad3d7f

    2024 doi

  7. [15]

    Applied and Computational Harmonic Analysis, 101850 (2025)

    Ni, H., Ying, L.: Quantum wave packet transforms with compact frequency support: Implemen- tations for wavelets and gabor atoms. Applied and Computational Harmonic Analysis, 101850 (2025)

    2025

  8. [16]

    Communications on Pure and Applied Mathematics58(11), 1472–1528 (2005)

    Candes, E.J., Demanet, L.: The curvelet representation of wave propagators is optimally sparse. Communications on Pure and Applied Mathematics58(11), 1472–1528 (2005)

    2005

  9. [17]

    Cand` es, E., Demanet, L.: Curvelets and fourier integral operators. C. R. Math. Acad. Sci. Paris 336(5), 395–398 (2003)

    2003

  10. [18]

    Society for Industrial and Applied Mathematics, USA 31 (1992)

    Daubechies, I.: Ten Lectures on Wavelets. Society for Industrial and Applied Mathematics, USA 31 (1992)

    1992

  11. [19]

    Academic Press, Inc., USA (2008)

    Mallat, S.: A Wavelet Tour of Signal Processing, Third Edition: The Sparse Way, 3rd edn. Academic Press, Inc., USA (2008)

    2008

  12. [20]

    variations on a theme

    Daubechies, I.: Orthonormal bases of compactly supported wavelets II. variations on a theme. SIAM J. Math. Anal.24(2), 499–519 (1993)

    1993

  13. [21]

    CSEG Recorder19(7), 8–9 (1994)

    Ryan, H.: Ricker, ormsby, klander, butterworth – a choice of wavelets. CSEG Recorder19(7), 8–9 (1994)

    1994

  14. [22]

    part 1: The analysis of information

    Gabor, D.: Theory of communication. part 1: The analysis of information. Journal of the Institution of Electrical Engineers - Part III: Radio and Communication Engineering93(26), 429–441 (1946) https://doi.org/10.1049/ji-3-2.1946.0074

    1946

  15. [23]

    Cambridge University Press, Cambridge, UK (2010)

    Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, Cambridge, UK (2010)

    2010

  16. [24]

    Physical Review A99(1), 012323 (2019)

    Costa, P.C., Jordan, S., Ostrander, A.: Quantum algorithm for simulating the wave equation. Physical Review A99(1), 012323 (2019)

    2019

  17. [25]

    https://arxiv.org/abs/2306.11802

    Bagherimehrab, M., Nakaji, K., Wiebe, N., Aspuru-Guzik, A.: Fast quantum algorithm for differential equations (2023). https://arxiv.org/abs/2306.11802

    2023

  18. [26]

    Physical Review Letters103(15) (2009) https://doi.org/10.1103/physrevlett.103.150502

    Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Physical Review Letters103(15) (2009) https://doi.org/10.1103/physrevlett.103.150502

    2009 doi

  19. [27]

    arXiv preprint arXiv:2411.02522 (2024)

    Morales, M.E., Pira, L., Schleich, P., Koor, K., Costa, P., An, D., Aspuru-Guzik, A., Lin, L., Reben- trost, P., Berry, D.W.: Quantum linear system solvers: A survey of algorithms and applications. arXiv preprint arXiv:2411.02522 (2024)

    2024 arXiv

  20. [28]

    Journal of Physics A: Mathematical and Theoretical47(10), 105301 (2014)

    Berry, D.W.: High-order quantum algorithm for solving linear differential equations. Journal of Physics A: Mathematical and Theoretical47(10), 105301 (2014)

    2014

  21. [29]

    Proceedings of the National Academy of Sciences115(38), 9456–9461 (2018)

    Childs, A.M., Maslov, D., Nam, Y., Ross, N.J., Su, Y.: Toward the first quantum simulation with quantum speedup. Proceedings of the National Academy of Sciences115(38), 9456–9461 (2018)

    2018

  22. [30]

    Quantum 8, 1553 (2024)

    Jennings, D., Lostaglio, M., Lowrie, R.B., Pallister, S., Sornborger, A.T.: The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts. Quantum 8, 1553 (2024)

    2024

  23. [31]

    Physical review letters110(25), 250504 (2013)

    Clader, B.D., Jacobs, B.C., Sprouse, C.R.: Preconditioned quantum linear system algorithm. Physical review letters110(25), 250504 (2013)

    2013

  24. [32]

    In: Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, pp

    Berry, D.W., Childs, A.M., Cleve, R., Kothari, R., Somma, R.D.: Exponential improvement in preci- sion for simulating sparse hamiltonians. In: Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, pp. 283–292 (2014)

    2014

  25. [33]

    Physical Review A105(2) (2022) https://doi.org/10.1103/ physreva.105.022415

    Kiani, B.T., De Palma, G., Englund, D., Kaminsky, W., Marvian, M., Lloyd, S.: Quantum advan- tage for differential equation analysis. Physical Review A105(2) (2022) https://doi.org/10.1103/ physreva.105.022415

    2022

  26. [34]

    In: Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, pp

    Liu, Y.-K.: Quantum algorithms using the curvelet transform. In: Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, pp. 391–400 (2009)

    2009

  27. [35]

    https://arxiv.org/abs/2310.03735 32

    Liu, Y.-K.: An Uncertainty Principle for the Curvelet Transform, and the Infeasibility of Quantum Algorithms for Finding Short Lattice Vectors (2023). https://arxiv.org/abs/2310.03735 32

    2023 arXiv

  28. [36]

    Journal of Mathematical Physics43(9), 4445–4451 (2002) https://doi.org/10.1063/1.1495899

    Harrow, A.W., Recht, B., Chuang, I.L.: Efficient discrete approximations of quantum gates. Journal of Mathematical Physics43(9), 4445–4451 (2002) https://doi.org/10.1063/1.1495899

    2002 doi

  29. [37]

    Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences469(2153), 20120686 (2013) https://doi.org/10.1098/rspa.2012.0686

    Beals, R., Brierley, S., Gray, O., Harrow, A.W., Kutin, S., Linden, N., Shepherd, D., Stather, M.: Effi- cient distributed quantum computing. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences469(2153), 20120686 (2013) https://doi.org/10.1098/r...

    2013

  30. [38]

    Physical Review A54(1), 147–153 (1996) https://doi.org/10.1103/physreva.54.147

    Vedral, V., Barenco, A., Ekert, A.: Quantum networks for elementary arithmetic operations. Physical Review A54(1), 147–153 (1996) https://doi.org/10.1103/physreva.54.147

    1996 doi

  31. [39]

    https://arxiv.org/abs/quant-ph/0410184

    Cuccaro, S.A., Draper, T.G., Kutin, S.A., Moulton, D.P.: A new quantum ripple-carry addition circuit (2004). https://arxiv.org/abs/quant-ph/0410184

    2004 arXiv

  32. [40]

    https://arxiv.org/abs/quant-ph/0008033

    Draper, T.G.: Addition on a Quantum Computer (2000). https://arxiv.org/abs/quant-ph/0008033

    2000 arXiv

  33. [41]

    https: //arxiv.org/abs/quant-ph/0201067

    Coppersmith, D.: An approximate Fourier transform useful in quantum factoring (2002). https: //arxiv.org/abs/quant-ph/0201067

    2002 arXiv

  34. [42]

    In: Auslander, L., Kailath, T., Mitter, S.K

    Coifman, R.R., Meyer, Y., Wickerhauser, V.: Wavelet analysis and signal processing. In: Auslander, L., Kailath, T., Mitter, S.K. (eds.) Signal Processing, Part I: Signal Processing Theory, pp. 59–68. Springer, New York, NY (1990). http://citeseer.nj.nec.com/coifman92wavelet.ht...

    1990

  35. [43]

    This produces: P2L−1 q=0 ˆf[q]|q L−1⟩ |qL−2⟩

    ApplyQ † L (equivalent to DFT). This produces: P2L−1 q=0 ˆf[q]|q L−1⟩ |qL−2⟩. . .|q0⟩

  36. [44]

    , L−2, apply controlled-Xgate to qubiticontrolled on qubitL−1

    For eachi= 0, . . . , L−2, apply controlled-Xgate to qubiticontrolled on qubitL−1. This produces the state: 2L−1X q=0 ˆf[q]|q L−1⟩ |qL−2 ⊕q L−1⟩. . .|q0 ⊕q L−1⟩

  37. [45]

    This produces the state: 2L−1X q=0 ˆf[q]|q L−2 ⊕q L−1⟩

    Cyclic shift ofLqubits implemented by SW AP gates. This produces the state: 2L−1X q=0 ˆf[q]|q L−2 ⊕q L−1⟩. . .|q0 ⊕q L−1⟩ |qL−1⟩ Frequency encoding (after applying the DFT) is carried out by Algorithm 2; decoding is performed by reversing the steps. The retaining decoding proc...

  38. [46]

    , j−1, applyXgate to qubiticontrolled on qubit 0

    For each qubiti= 1, . . . , j−1, applyXgate to qubiticontrolled on qubit 0. This produces the state: |m0⟩ 2j −1X q=0 αq |qj−1 ⊕q 0⟩. . .|q1 ⊕q 0⟩ |q0⟩

  39. [47]

    This produces the state: |m0⟩ 2j −1X q=0 αq |q0⟩ |qj−1 ⊕q 0⟩

    Cyclic shift ofjqubits implemented by SW AP gates. This produces the state: |m0⟩ 2j −1X q=0 αq |q0⟩ |qj−1 ⊕q 0⟩. . .|q1 ⊕q 0⟩

  40. [48]

    This produces the state: |m0⟩ 2j −1X q=0 αq |q0 ⊕m 0⟩ |qj−1 ⊕q 0⟩

    ApplyXgate to qubitj−1 controlled on qubitj. This produces the state: |m0⟩ 2j −1X q=0 αq |q0 ⊕m 0⟩ |qj−1 ⊕q 0⟩. . .|q1 ⊕q 0⟩. Combined: ˜d(q, j, m) =˜d(qj−1 , qj−2 , . . . , q0;j;m) = (q 0 ⊕m),(q j−1 ⊕q 0), . . . ,(q1 ⊕q 0). The description of the algorithm has the evolution o...

  41. [51]

    ,Rq[j−1] controlled onR h[j] =|1⟩

    For each integerjstarting fromj=Ltillj= 1, apply QFT rotationQ R j to qubitsR q[0], . . . ,Rq[j−1] controlled onR h[j] =|1⟩

  42. [53]

    This is feasible because the action of steps 2-4 on the registerR q is block-diagonal, i.e., it preserves each subspace span{|q⟩ |˜h(q) =j}

    Undo the computation of step 1, returning the registerR h to the state|0⟩. This is feasible because the action of steps 2-4 on the registerR q is block-diagonal, i.e., it preserves each subspace span{|q⟩ |˜h(q) =j}. ProofLet us consider the evolution of| ˆf⟩within the subspace...

  43. [54]

    After the second step, the state is X ˜h(q)=j ˆf[d(q)] qL−1

    0⟩. After the second step, the state is X ˜h(q)=j ˆf[d(q)] qL−1 . . . qj ˜d(qj−1 . . . q0, j, qj ) E |1. . .10. . .0⟩. Steps 3-4 apply QFT ofj-qubits to the state, which results in X ˜h(q)=j qL−1 . . . qj  2−j/2 2j −1X n=0 ˆf[d(q)]e i2−j n· ˜d(qj−1 ...q0,j,qj ) |n⟩   |1. ....

  44. [55]

    Apply gateR 0 to qubitR q[0]

  45. [56]

    hL−1(q)⟩, in other words, qubitR h[i] is in state|h i(q)⟩

    Computeh j, 1≤j < L, by calling subroutines such that for basis state|q⟩ |q⟩|{z} Rq |0⟩|{z} Rh 7→ |q⟩ |h1(q)h2(q). . . hL−1(q)⟩, in other words, qubitR h[i] is in state|h i(q)⟩

  46. [57]

    , L−1 apply (−iZ)-gate to qubitRq[0] controlled onR q[j] =|1⟩,R h[j] =|1⟩and Rh[j+ 1] =|0⟩(forj=L−1, the latter condition is omitted)

    For eachj= 1, . . . , L−1 apply (−iZ)-gate to qubitRq[0] controlled onR q[j] =|1⟩,R h[j] =|1⟩and Rh[j+ 1] =|0⟩(forj=L−1, the latter condition is omitted)

  47. [58]

    , L−1 apply decoding circuit˜Dj to qubitsR q[0],

    For eachj= 1, . . . , L−1 apply decoding circuit˜Dj to qubitsR q[0], . . . ,Rq[j] controlled onR h[j] =|1⟩ andR h[j+1] =|0⟩(forj=L−1, the latter condition is omitted and ˜Dj is applied toR q[0], . . . ,Rq[j− 1])

  48. [59]

    , L−1, and eachi= 0,

    For eachj= 1, . . . , L−1, and eachi= 0, . . . , j−1, applyPj−i+1 gate toR q[i] controlled onR h[j] =|1⟩ andR h[j+ 1] =|0⟩

  49. [60]

    ,Rq[j−1] controlled on qubitR h[j] =|1⟩

    For each integerjstarting fromj=Ltoj= 1, apply QFT rotationQ R j to qubitsR q[0], . . . ,Rq[j−1] controlled on qubitR h[j] =|1⟩

  50. [61]

    , Lapply QFT swapQS j to qubitsR q[0],

    For eachj= 2, . . . , Lapply QFT swapQS j to qubitsR q[0], . . . ,Rq[j−1] controlled onR h[j] =|1⟩ andR h[j+ 1] =|0⟩(the latter condition is omitted forj=L−1)

  51. [62]

    This is feasible because the action of steps 3-7 on the registerR q is block-diagonal, i.e., it preserves each subspace span{|q⟩ |˜h(q) =j}

    Undo the computation of step 2, returning the registerR h to the state|0⟩. This is feasible because the action of steps 3-7 on the registerR q is block-diagonal, i.e., it preserves each subspace span{|q⟩ |˜h(q) =j}. Proof of correctness of Algorithm 5Let’s consider the evoluti...

  52. [63]

    After the third step, the state is X ˜h(q)=j (−1)q0∨qj iqj e(−1)q0 +1iπ/4 ˆf[d(q)]|q⟩ |1

    ⟩. After the third step, the state is X ˜h(q)=j (−1)q0∨qj iqj e(−1)q0 +1iπ/4 ˆf[d(q)]|q⟩ |1. . .10. . .0⟩. After the fourth step, the state is X ˜h(q)=j (−1)q0∨qj iqj e(−1)q0 +1iπ/4 ˆf[d(q)]|q L−1⟩. . . qj ⊗ |˜d(qj−1 . . . q0, k, qj ⟩ |1. . .10. . .0⟩. After the fifth step, th...

  53. [64]

    ApplyS-gate toR q[0]

  54. [65]

    hL−1(q)⟩ |0⟩, in other words, qubitR h[i] is in the state|h i(q)⟩

    Computeh j, 1≤j < L, by calling subroutines such that for basis state|q⟩ |q⟩|{z} Rq |0⟩|{z} Rh |0⟩|{z} RI 7→ |q⟩ |h1(q). . . hL−1(q)⟩ |0⟩, in other words, qubitR h[i] is in the state|h i(q)⟩

  55. [66]

    , L−1 controlled onRh[j] =|1⟩,R h[j+ 1] =|0⟩: (a) Compute Comparator j−1(µ0(j,0) + 1) applied to qubitsR q[1],

    For eachj= 1, . . . , L−1 controlled onRh[j] =|1⟩,R h[j+ 1] =|0⟩: (a) Compute Comparator j−1(µ0(j,0) + 1) applied to qubitsR q[1], . . . ,Rq[j−1] with the result added toR I ancilla qubit. (b) Apply linear Pauli rotation (see Figure 15) with slope of 3π2 −j and offset of−πcont...

  56. [67]

    This is feasible because the action of step 3 on the registerR q is block-diagonal, i.e., it preserves each subspace span{|q⟩ |˜h(q) = j}

    Undo the computation of step 2, returning the registerR h to the state|0⟩. This is feasible because the action of step 3 on the registerR q is block-diagonal, i.e., it preserves each subspace span{|q⟩ |˜h(q) = j}

  57. [68]

    Proof of correctness of Algorithm 6For the proof, let us denote R(θ) = cos(θ) sin(θ) −sin(θ) cos(θ)

    Apply inverseS-gate toR q[0]. Proof of correctness of Algorithm 6For the proof, let us denote R(θ) = cos(θ) sin(θ) −sin(θ) cos(θ) . 38 Let’s consider the evolution within the subspace span{|q⟩ | ˜h(q) =j}for a fixedj, in other words, X m s.t.Wj m∈ΛT 2j−1 −1X n=0 |m2j−1 +n⟩(α m...

  58. [69]

    After step 3a, the state is X m s.t.Wj m∈ΛT 2j−1 −1X n=0 |m2j−1 +n⟩(α m2j +2n |0⟩+iα m2j +2n+1 |1⟩)|1

    0⟩ |0⟩. After step 3a, the state is X m s.t.Wj m∈ΛT 2j−1 −1X n=0 |m2j−1 +n⟩(α m2j +2n |0⟩+iα m2j +2n+1 |1⟩)|1. . .10. . .0⟩ ⊗ |I(n≥µ0(j,0) + 1)⟩. Note thatI(n≥µ 0(j,0) + 1) =I(n >2 j /3) asn, j∈Z. After step 3b, the state is X m s.t.Wj m∈ΛT 2j−1 −1X n=0 |m2j−1 +n⟩ ⊗ R π 2j+1 (...

  59. [70]

    , hL−1(q)⟩ |0⟩

    Computeh j, 1≤j < L, by calling subroutines on the registerR q and ancilla qubitR I [0] as the least significant qubit, |q⟩|{z} Rq |0⟩|{z} R′ h |0⟩|{z} Rh |0⟩|{z} RI 7→ |q⟩ |0⟩ |h1(q), . . . , hL−1(q)⟩ |0⟩

  60. [71]

    Apply Compare L−1(µ0(jl,0) + 1) toR q with the result added toR I [0]

  61. [72]

    Apply Compare L−1(mr2jr−1 +µ 0(jr, mr) + 1) toR q with the result added toR I [0]

  62. [73]

    For eachj= 2, . . . , L−1 controlled on thatRh[j] =|1⟩,R h[j+ 1] =|0⟩andR I [0] =|1⟩: (a) Apply Compare j(µ0(j,0) + 1) to the firstj−1 qubits inR q controlled on thatR q[j−1] =|0⟩and add the result toR I [1]; (b) Apply Compare j(µ0(j,1) + 1) to the firstj−1 qubits inR q contro...

  63. [74]

    Un-compute steps 3, 2, 1. Proof of correctness of Algorithm 7HereRI [0] =|1⟩allows us to avoid permuting the border cases and computed in steps 2-3.R I [1] =|1⟩computed in step 4a-4b controls the conditionn > µ(j, m). This condition depends on the parity ofmwhich is equal toR ...

Pith tools

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