Pith. sign in

REVIEW 1 major objections 5 minor 1 cited by

QRTlib: A Library for Fast Quantum Real Transforms

T0 review · 1 major / 5 minor · reviewed 2026-08-04 · deepseek-v4-flash

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

Pith's one-line read The quantum Hartley transform can be implemented with about half the log-squared gate count of the previous best algorithm, matching the asymptotic cost of the quantum Fourier transform.

desk verdict The LCU-based QHT is a genuine new construction; the optimized QST-I needs a domain qualifier before its claims are accurate. read the letter →

arxiv 2510.16625 v2 pith:NWBXCH55 submitted 2025-10-18 quant-ph cs.ETcs.MScs.SYeess.SY

Armin Ahmadkhaniha , Lu Chen , Jake Doliskani , Zhifu Sun This is my paper · ORCID
classification quant-phcs.ETcs.MScs.SYeess.SY MSC 81P68
keywords quantumrealtransformsHartleytransformcosinesinelinearcombinationofunitariesamplitudeamplificationtwo'scomplementcircuitoptimization
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 makes quantum real transforms practical rather than theoretical. It shows that the quantum Hartley transform reduces to a linear combination of two unitaries — the identity and a two's-complement operation — followed by a Fourier transform, and that a single round of a modified oblivious amplitude amplification implements it exactly. The resulting circuit uses 1/2 log^2 N + O(log N) gates, roughly four times fewer than the prior best. It also constructs a Type-I sine transform with the same gate count that eliminates the large multi-controlled gates in earlier constructions, and packages the transforms as the first complete, executable circuit library for quantum Hartley, cosine, and sine transforms.

What carries the argument

The key object is the identity F_N T = F_N^*, which expresses the inverse Fourier transform as the Fourier transform followed by two's complement, and the resulting Hartley decomposition as a two-term linear combination of unitaries. The LCU construction with oblivious amplitude amplification (using the angle-shifted variant with an extra ancilla) converts that linear combination into a deterministic circuit. For the Type-I sine transform, the supporting identity is T_N^* F_{2N} T_N = C_N^I xor i S_N^I, together with the domain restriction that the sine transform only acts on indices 1 through N-1, which removes the need to detect the all-zero data register. The paper's optimized two's-compl

What would settle it

For a small case such as N=8, construct the full (n+1)-qubit unitary matrix of the QST-I circuit and check unitarity on all computational basis states; in particular, run Algorithm 4 on |0>|0^n> and on |0>|1^n> and measure whether the ancilla is cleanly returned to |0> with no amplitude loss. If the operator is not unitary or the ancilla does not disentangle, the domain-support assumption is violated.

Watch

Extended reading notes

Core claim

The central discovery is that the Hartley transform can be written as H_N = QFT_N * V, where V = (e^{-i pi/4} I + e^{i pi/4} T)/sqrt(2) and T is the two's-complement permutation. Because V is a linear combination of just two unitaries, the LCU framework applies with a single ancilla and a Hadamard encoding; the paper shows that after using an extra ancilla and a modified amplitude-amplification angle, one round of oblivious amplitude amplification yields V exactly. The dominant cost is then the QFT itself, giving 1/2 log^2 N + O(log N) gates. For the Type-I sine transform, the paper observes that the sine basis has zero amplitude on indices 0 and N, so the controlled non-zero check used in p

Load-bearing premise

The optimized Type-I sine circuit is exact only when the input state has zero amplitude on the basis states |0> and |N>; on arbitrary inputs the advertised map is not unitary, so the whole QST-I contribution rests on that domain restriction.

Editorial extensions

If this is right

  • The quantum Hartley transform becomes competitive with the quantum Fourier transform in gate count, making real-valued quantum signal processing substantially cheaper than previously believed.
  • The Type-I sine transform can be executed without large multi-controlled gates, which should reduce circuit depth and error rates on near-term hardware.
  • The library provides, for the first time, executable quantum circuits for the Hartley transform and for Type I–IV cosine and sine transforms, rather than only theoretical constructions.
  • The reusable two's-complement and or-tree subroutines give a low-overhead blueprint for other arithmetic and controlled-operation circuits in quantum computing.

Reading between the lines

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

  • Because Algorithm 4 is unitary only on the sine-subspace (indices 1 to N-1), a natural extension is to pair it with a projection or phase-estimation step that filters out the |0> and |N> amplitude, so it could be applied to arbitrary input states.
  • The same LCU-plus-two's-complement strategy may generalize to other real transforms that can be written as short linear combinations of Fourier transforms and permutation unitaries, potentially yielding similar gate reductions for DCT variants.
  • The paper reports gate counts, not circuit depth; whether the fourfold gate reduction translates to a comparable depth reduction on hardware depends on how the QFT and the two's-complement subcircuits are laid out and parallelized.
  • If the corrected Type-IV identity in Appendix B is representative, a systematic audit of previously published quantum real-transform identities may uncover further simplifications or corrections.
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

1 major / 5 minor

Summary. The paper introduces QRTlib, a Qiskit library for quantum real transforms (Hartley, cosine, and sine transforms of types I–IV). Its main theoretical contributions are a new LCU-based quantum Hartley transform algorithm with claimed gate complexity 1/2 log² N + O(log N), advertised as a fourfold reduction over the recursive algorithm of [8], and an optimized Type-I quantum sine transform using QFT_{2N} with the same asymptotic complexity while avoiding large multi-controlled gates. The paper also presents circuit optimizations (two's-complement and or-tree constructions), implementations of Type II–IV transforms, a correction to a Type-IV identity from [11], and a link to GitHub code. The central derivations in Sections 3.3 and 4.3 are explicit, parameter-free, and algebraically checkable.

Significance. The LCU construction for the quantum Hartley transform is elegant and, if correct, gives the best asymptotic gate count for QHT known to this reader. The paper ships code, does not fit parameters, and re-derives the identities it needs; the F_N T = F*_N identity and the θ'=π/6 amplification step are verified in the text. The optimized QST-I algorithm is also useful, but only as an isometry on a proper subspace; with an explicit domain qualifier it would be a practical improvement. Overall, the work is a solid engineering contribution to a small literature, provided the domain issue identified below is fixed.

major comments (1)
  1. [§4.3, Algorithm 4, Theorem 4.1] The optimized QST-I circuit is derived only for basis states |a> with 1 ≤ a ≤ N−1. It is not a unitary on the full n-qubit space. For a=0, after Step 2 the state is (|0>−|1>)|0>/√2; QFT_{2N} maps this to a nonzero superposition over odd y, and the subsequent A_N^* = (H⊗I)P2C does not return the ancilla to |0>. Hence the ancilla is entangled and tracing it out does not produce QSTI_N|0>. Since QSTI_N as defined in Section 2 is (N−1)×(N−1), no unitary on N dimensions can implement it; the algorithm is an isometric embedding of span{|1>,...,|N−1>}. Theorem 4.1 ('Algorithm 4 applies QSTI_N') and Algorithm 4's 'Input: n-qubit state |ψ>' omit this support condition. The text's acknowledgment that 'the domain is restricted to indices 1,...,N−1' does not resolve the mismatch between the theorem and the circuit's stated input. Please restate the theorem and algorithm with the explicit domain, des
minor comments (5)
  1. [§4.3, displayed derivation] The line 'i|1>QSTI_N −1|a>' appears to be a typo: the state has N−1 terms and is the QSTI_N output for a ∈ {1,...,N−1}. The subscript should be N, not N−1.
  2. [§4.2, or-tree reset discussion] The sentence saying that resetting the final or-tree ancilla requires 'a complete second or-tree evaluation' is misleading. Each OR gate is self-inverse, so reversing the computation (including the root gate) resets all ancillas; no second forward evaluation is needed. The gate-count discussion should be corrected accordingly.
  3. [Algorithm 3, Steps 5–6] Please clarify the intended ordering of H and S and whether the S in Step 5 is S or S†. The D gate in Section 4.1 satisfies D = H S, so D† = S† H; as written, the sequence 'H and S' followed by an unconditional S† appears inconsistent with D† unless a specific (nonstandard) ordering convention is intended.
  4. [Various] The word 'trace out' in Algorithms 2 and 4 is not a circuit primitive; since the ancillas are claimed to be disentangled, 'discard' or 'ignore' is more accurate. This matters especially in Algorithm 4, where outside the valid domain the ancilla is not cleanly separated and the reduced state is mixed.
  5. [General] There are numerous typographical errors ('el-emntary', 'unitareis', 'complemtness', 'breifly', 'rwo', 'imepelementations'). A careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: parameter-free LCU and QFT derivations; minor non-load-bearing self-citation to [8].

full rationale

The derivation chain is self-contained and parameter-free. The new QHT algorithm (Section 3.3) starts from the trigonometric identity cas(x) = ((1-i)/2)w^x + ((1+i)/2)w^{-x}, derives H_N = F_N((e^{-i pi/4}/sqrt(2))1 + (e^{i pi/4}/sqrt(2))T) using F_N T = F_N^*, and then follows the standard LCU/oblivious-amplitude-amplification recipe (Appendix A, Lemmas A.1-A.2) with explicit angles theta = pi/4 and theta' = pi/6. No parameter is fitted to any target output; the 1/2 log^2 N + O(log N) count comes from the standard QFT gate count plus O(log N) for the two's-complement circuit. The QST-I algorithm (Section 4.3) is likewise an explicit algebraic derivation from QFT_{2N} and P2C, not an extraction from the claimed output. The comparison baseline [8] is self-cited (Doliskani is a co-author of both works), but it is used only as a complexity benchmark and as a prior technique; the correctness proofs do not invoke [8] as a black box. The only substantive caveat is the domain restriction acknowledged in Section 4.3: 'the domain is restricted to indices 1, 2, . . . , N-1' for DST-I. Algorithm 4 and Theorem 4.1 omit this qualifier when stating output on an arbitrary n-qubit state; for inputs containing |0> or |N> the map is an isometry rather than a full unitary and the ancilla may not cleanly disentangle. That is a correctness/domain issue, not a circularity. No fitted-input-called-prediction, uniqueness-imported-from-authors, ansatz-via-citation, or renaming pattern appears. The score of 2 reflects only the minor, non-load-bearing self-citation; the central derivations stand independently.

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

The central claims rely on standard quantum-circuit background and on one external adder construction; there are no fitted parameters and no new physical entities. The important domain assumption is the restricted input space for QST-I.

assumptions (4)
  • standard math LCU technique and oblivious amplitude amplification (Lemmas A.1 and A.2) are correct and apply to unitary V.
    Used in Section 3.3 and Appendix A; result from Childs-Wiebe [5] and Kothari [13].
  • standard math QFT on M qubits requires 1/2 log^2 M + O(log M) elementary gates.
    Background; used in Theorems 3.1 and 4.1.
  • domain assumption Fedoriaka's constant-adder circuit implements a conditional increment with O(log N) elementary gates and n−2 ancillas.
    Used in Section 3.2 for the optimized two's complement; not proved inside the paper.
  • domain assumption The optimized QST-I algorithm is only called on states with support on basis states |a> with 1 ≤ a ≤ N−1.
    Section 4.3 restricts the DST-I domain to indices 1..N−1; if input contains |0> or |N>, the circuit is not norm-preserving.

how reviews work

0 comments
Cite this review

Pith. "Pith review of QRTlib: A Library for Fast Quantum Real Transforms." pith.science (2026). https://pith.science/paper/NWBXCH55

@misc{pith2026251016625,
  author       = {Pith},
  title        = {Pith review of: QRTlib: A Library for Fast Quantum Real Transforms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NWBXCH55}},
  note         = {Machine review of arXiv:2510.16625}
}
read the original abstract

Real-valued transforms such as the discrete cosine, sine, and Hartley transforms play a central role in classical computing, complementing the Fourier transform in applications from signal and image processing to data compression. However, their quantum counterparts have not evolved in parallel, and no unified framework exists for implementing them efficiently on quantum hardware. This article addresses this gap by introducing QRTlib, a library for fast and practical implementations of quantum real transforms, including the quantum Hartley, cosine, and sine transforms of various types. We develop new algorithms and circuit optimizations that make these transforms efficient and suitable for near-term devices. In particular, we present a quantum Hartley transform based on the linear combination of unitaries (LCU) technique, achieving a fourfold reduction in circuit size compared to prior methods, and an improved quantum sine transform of Type I that removes large multi-controlled operations. We also introduce circuit-level optimizations, including two's-complement and or-tree constructions. QRTlib provides the first complete implementations of these quantum real transforms in Qiskit.

Figures

Figures reproduced from arXiv: 2510.16625 by the authors.

Figure 1
Figure 1. The circuit for inc5. The bi and ai represent the data and carry qubits, respectively. gates use ancillas to break down the operation to elementary gates. By contrast, using an ancilla register, the two’s comple￾ment operation can be implemented with O(log N) elemen￾tary gates. We have implemented an optimized version of this two’s complement operation that proceeds in the stan￾dard two steps: first, all qubits are … view at source ↗
Figure 2
Figure 2. Carry propagation for incn ure 2 is a snippet from our implementation, performing a carry propagation and recovery in the incn function. 3.3 A new QHT algorithm using LCU In this section, we propose a new QHTN algorithm that uti￾lizes a well-known technique called Linear Combination of Unitaries (LCU). We refer the reader to Appendix A for a brief overview of the LCU technique. Let T : ZN → ZN be the two’s complemen… view at source ↗
Figure 3
Figure 3. Unitary W for the LCU subroutine QHTN algorithm Gate complexity Klappenecker and Rotteler [ ¨ 12] (Using controlled-QFTN ) 5 2 log2 N + O(log N) Agaian and Klappenecker [1] (Recursive decomposition) 5 2 log2 N + O(log N) Doliskani, Mirzaei, and Mousavi [8] (Recusive decomposition) 2 log2 N + O(log N) This work (using LCU) 1 2 log2 N + O(log N) [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (9 more)
Figure 5
Figure 5. Figure 5: Implementation of the or-gate. This root ancilla thus encodes whether the entire register is non-zero, and can be used to control the application of the S and H gates on the control qubit within the D gate construc￾tion [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]
Figure 6
Figure 6. Figure 6: or-gate tree for 4 qubits. The qi and ai are the data and ancilla qubits, respectively. This or-tree method requires exactly n − 1 ancilla qubits to perform a complete binary reduction over n data qubits. Each or operation consists of two cnot gates and one Toffoli gat…
Figure 4
Figure 4. Figure 4: Circuit for or. This or gate works as follows: first, each data qubit applies a cnot gate to the ancilla, flipping it if that qubit is in the |1⟩ state. Then, a Toffoli gate is applied using both data qubits as controls and the same ancilla as the target. The ancilla f…
Figure 7
Figure 7. Figure 7: The main loop for the implementation of the [PITH_FULL_IMAGE:figures/full_fig_p008_7.png]
Figure 8
Figure 8. Figure 8: Implementation of the unitary AN . Proof. The QFT2N has gate complexity 1 2 log2 N +O(log N). All other unitaries in the algorithm can be implemented using O(log N) elementary gates. The snippet in [PITH_FULL_IMAGE:figures/full_fig_p009_8.png]
Figure 10
Figure 10. Figure 10: Implementation of the unitary G. The ancilla qubit contains the result of the or-tree evaluation. where F2N is the Fourier transform. In the quantum setting, the above identity is expressed as M·U T N ·QFT2N ·UN = |0⟩⟨0|⊗QCTIV N −i|1⟩⟨1|⊗QSTIV N , (6) Simillar to the …
Figure 9
Figure 9. Figure 9: Circuit for the unitary D1. followed by an S gate to the main control qubit. If the or￾tree output evaluates to zero, we further apply the sequence of gates S ∗ , H, and another S ∗ to reverse the initial rotation. Notably, since the or-gate tree is used exactly once i…
Figure 11
Figure 11. Figure 11: Circuit for the unitary D2. The snippet in [PITH_FULL_IMAGE:figures/full_fig_p011_11.png]
Figure 12
Figure 12. Figure 12: Implementation of the digonal gates Ki and Li used in the unitary D1 and D2. A Linear Combination of Unitaries (LCU) In this section, we briefly review the LCU technique, follow￾ing the expositions in [5, 13]. Let U1, . . . , UM be a set of unitaries acting on a N-dim…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Encoding Choices and Fault-Tolerant Resource Estimates for Digital Quantum Hamiltonian Descent

    quant-ph 2026-07 conditional novelty 6.0 of 10

    For digital quantum Hamiltonian descent, binary amplitude encoding uses O(d log N) qubits and fewer R_z rotations than one-hot encoding in all tested benchmarks, making it the preferred starting point for fault-tolera...

Reference graph

Works this paper leans on

20 extracted references · 3 linked inside Pith · cited by 1 Pith paper

  1. [8]

    Public-key quantum money and fast real transforms

    Jake Doliskani, Morteza Mirzaei, and Ali Mousavi. Public-key quantum money and fast real transforms. arXiv preprint arXiv:2503.18890, 2025

    arXiv 2025

  2. [11]

    Discrete co- sine transforms on quantum computers

    Andreas Klappenecker and Martin Rotteler. Discrete co- sine transforms on quantum computers. In ISPA 2001. Proceedings of the 2nd International Symposium on Image and Signal Processing and Analysis. In conjunction with 23rd International Conference on Information Technology Interfaces (IEEE Cat., pages 464–468. IEEE, 2001

    2001

  3. [1]

    Agaian and Andreas Klappenecker

    Sos S. Agaian and Andreas Klappenecker. Quantum computing and a unified approach to fast unitary trans- forms. In Image Processing: Algorithms and Systems, vol- ume 4667, pages 1–11. SPIE, 2002

    2002

  4. [2]

    Dis- crete cosine transform

    Nasir Ahmed, T Natarajan, and Kamisetty R Rao. Dis- crete cosine transform. IEEE transactions on Computers , 100(1):90–93, 2006

    2006

  5. [3]

    Discrete hartley transform

    Ronald N Bracewell. Discrete hartley transform. Journal of the Optical Society of America, 73(12):1832–1835, 1983

    1983

  6. [4]

    Spectral methods: fundamentals in single domains

    Claudio Canuto, M Youssuff Hussaini, Alfio Quarteroni, and Thomas A Zang. Spectral methods: fundamentals in single domains. Springer

  7. [5]

    Hamiltonian sim- ulation using linear combinations of unitary operations

    Andrew M Childs and Nathan Wiebe. Hamiltonian sim- ulation using linear combinations of unitary operations. Quantum Information and Computation, 12(11&12):901– 924, 2012

    2012

  8. [6]

    Quantum algorithms revisited

    Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca. Quantum algorithms revisited. Proceed- ings of the Royal Society of London. Series A: Mathemat- ical, Physical and Engineering Sciences , 454(1969):339– 354, 1998

    1969

Show all 20 references
  1. [7]

    Fast parallel circuits for the quantum fourier transform

    Richard Cleve and John Watrous. Fast parallel circuits for the quantum fourier transform. In Proceedings 41st Annual Symposium on Foundations of Computer Science , pages 526–536. IEEE, 2000

    2000

  2. [9]

    New circuit for quantum adder by constant

    Dmytro Fedoriaka. New circuit for quantum adder by constant. arXiv preprint arXiv:2501.07060, 2025

    2025 arXiv

  3. [10]

    An introduction to quantum computing

    Phillip Kaye, Raymond Laflamme, and Michele Mosca. An introduction to quantum computing . OUP Oxford, 2006

    2006

  4. [12]

    On the irre- sistible efficiency of signal processing methods in quan- tum computing

    Andreas Klappenecker and Martin R ¨otteler. On the irre- sistible efficiency of signal processing methods in quan- tum computing. arXiv preprint quant-ph/0111039, 2001

    2001 arXiv

  5. [13]

    Efficient algorithms in quantum query complexity

    Robin Kothari. Efficient algorithms in quantum query complexity. PhD thesis, University of Waterloo Canada, 2014

    2014

  6. [14]

    Signal and image compression using quantum discrete cosine transform

    Chao-Yang Pang, Ri-Gui Zhou, Ben-Qiong Hu, WenWen Hu, and Ahmed El-Rafei. Signal and image compression using quantum discrete cosine transform. Information Sciences, 473:121–141, 2019

    2019

  7. [15]

    Quantum discrete cosine transform for image compres- sion

    Chao Yang Pang, Zheng Wei Zhou, and Guang Can Guo. Quantum discrete cosine transform for image compres- sion. arXiv preprint quant-ph/0601043, 2006

    2006 arXiv

  8. [16]

    JPEG: Still image data compression standard

    William B Pennebaker and Joan L Mitchell. JPEG: Still image data compression standard . Springer Science & Business Media, 1992

    1992

  9. [17]

    Discrete cosine trans- form: algorithms, advantages, applications

    K Ramamohan Rao and Ping Yip. Discrete cosine trans- form: algorithms, advantages, applications . Academic press, 2014

    2014

  10. [18]

    The transform and data compression handbook

    Kamisetty Ramam Rao and Patrick C Yip. The transform and data compression handbook . CRC press, 2018

    2018

  11. [19]

    Algorithms for quantum computation: discrete logarithms and factoring

    Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science , pages 124–134. Ieee, 1994

    1994

  12. [20]

    Quantum circuit design of discrete hartley transform using recur- sive decomposition formula

    Chien-Cheng Tseng and Tsung-Ming Hwang. Quantum circuit design of discrete hartley transform using recur- sive decomposition formula. In 2005 IEEE International Symposium on Circuits and Systems (ISCAS) , pages 824–

    2005

Pith tools

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