pith. sign in

arxiv: 2411.14434 · v2 · submitted 2024-11-02 · 🪐 quant-ph · cs.CR

Quantum CORDIC -- Arcsine on a Budget

Iain Burge , Michel Barbeau , Joaquin Garcia-Alfaro This is my paper

Pith reviewed 2026-05-23 17:57 UTC · model grok-4.3

classification 🪐 quant-ph cs.CR
keywords quantum CORDICarcsinereversible quantum algorithmsquantum trigonometric functionsHHL algorithmquantum Monte Carlo
0
0 comments X

The pith

A reversible quantum CORDIC algorithm computes the arcsine function using O(n) qubits for n-bit precision.

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

The paper introduces a quantum version of the CORDIC algorithm to compute arcsine with arbitrary accuracy. It replaces non-reversible operations with fully reversible quantum equivalents. This achieves space complexity of O(n) qubits, depth O(n log n), and O(n squared) CNOT gates. Such a primitive supports algorithms like HHL and quantum Monte Carlo methods.

Core claim

The authors detail multiple approaches to calculate the arcsine function reversibly with CORDIC, establishing that for n bits of precision the method requires order n qubits, order n log n layers, and order n squared CNOTs while avoiding non-reversible operations.

What carries the argument

The reversible CORDIC iteration adapted for quantum circuits, which uses bit shifts and additions implemented reversibly to approximate trigonometric functions.

If this is right

  • Provides a required step for the Harrow-Hassidim-Lloyd algorithm.
  • Supports quantum digital-to-analog conversion.
  • Simplifies quantum speed-ups for Monte-Carlo methods.
  • Enables direct applications in quantum estimation of Shapley values.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar reversible adaptations could apply to other elementary functions computable by CORDIC such as arctangent or square root.
  • The stated bounds allow direct substitution into larger quantum circuits without changing their leading asymptotic costs.
  • Hardware implementations could test the layer and CNOT counts on small-scale quantum processors for moderate n.

Load-bearing premise

Non-reversible operations in classical CORDIC can be replaced by fully reversible quantum equivalents without increasing the asymptotic resource counts.

What would settle it

An explicit circuit construction or simulation for small n that requires more than O(n squared) CNOTs or fails to achieve the claimed precision would falsify the resource claims.

Figures

Figures reproduced from arXiv: 2411.14434 by Iain Burge, Joaquin Garcia-Alfaro, Michel Barbeau.

Figure 1
Figure 1. Figure 1: This would give us state, R |ψ1⟩ = |ψ2⟩ = L X−1 k=0 αk |hk⟩in |arcsin p hk⟩aux ·  cos  arcsin p hk  |0⟩ + sin  arcsin p hk  |1⟩  out . Using trigonometry identities, we have that, |ψ2⟩ = LX−1 k=0 αk |hk⟩in |arcsin p hk⟩aux · p 1 − hk |0⟩ + p hk |1⟩  out . . . . . . . · · · |arcsin √ hk⟩aux |0⟩out Ry π 4  Ry π 8  Ry π 2n+1  [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Unitary transformation R′ which transfers the binary encoding of CORDIC rotation direction stored d register into the amplitude of the out register. Define Ry(ω) = (cos ω, − sin ω; sin ω, cos ω), and µi = tan−1 2 −i . VII. COMPLEXITY AND SIMULATIONS In this section, we detail the complexity to construct |κ2⟩, Equation (2). The quantum implementation of Algorithm 1, skipping Line 10, applies Mult three time… view at source ↗
Figure 3
Figure 3. Figure 3: Results of Classical simulations of Quantum compatible Algorithm for CORDIC Arcsine (see our GitHub repository at [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
read the original abstract

This work introduces a quantum algorithm for computing the function arcsine, with arbitrary accuracy. We leverage a technique from embedded computing and Field-Programmable Gate Arrays, called COordinate Rotation DIgital Computer (CORDIC). CORDIC is a family of iterative algorithms that, in a classical context, can approximate various trigonometric, hyperbolic, and elementary functions using only bit shifts and additions. Adapting CORDIC to the quantum context is non-trivial, as the algorithm traditionally uses several non-reversible operations. We detail a method for CORDIC that avoids such non-reversible operations. We propose multiple approaches to calculate the arcsine function reversibly with CORDIC. For n bits of precision, our method has space complexity of order n qubits, a layer count in the order of n times log n, and a CNOT count in the order of n squared. This primitive function is a required step for the Harrow-Hassidim-Lloyd (HHL) algorithm, is necessary for quantum digital-to-analog conversion, can simplify a quantum speed-up for Monte-Carlo methods, and has direct applications in the quantum estimation of Shapley values.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The manuscript introduces a reversible quantum adaptation of the classical CORDIC algorithm to compute the arcsine function to arbitrary precision. It asserts that multiple reversible approaches exist and claims that, for n bits of precision, the construction uses O(n) qubits, O(n log n) layers, and O(n²) CNOT gates. The work positions this primitive as relevant to HHL, quantum digital-to-analog conversion, Monte-Carlo speed-ups, and Shapley-value estimation.

Significance. If the stated resource bounds can be rigorously established, the result would supply a useful, asymptotically efficient quantum primitive for arcsine that avoids the overhead of general function-approximation techniques. The applications listed are standard motivations for such a primitive.

major comments (2)
  1. [Abstract] Abstract: the central complexity claim (O(n) qubits, O(n log n) layers, O(n²) CNOTs) is asserted without any explicit reversible circuit construction, gate-sequence accounting, or analysis of ancilla overhead and uncomputation costs required to replace the classical non-reversible conditional rotations and sign decisions.
  2. [Abstract] Abstract: the statement that 'multiple approaches' exist to make CORDIC fully reversible is not accompanied by even a high-level description of how the iterative shifts, adds, and decision logic are realized reversibly while preserving the claimed asymptotics; without this, the load-bearing step from classical CORDIC to the quoted quantum costs cannot be verified.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed review and for highlighting opportunities to improve clarity in the abstract. The full manuscript contains explicit reversible circuit constructions, gate accounting, and ancilla analysis in Sections 3–5; the abstract was intentionally kept concise. We will revise the abstract to incorporate high-level descriptions and section references while preserving the stated asymptotics, which follow directly from the constructions provided.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central complexity claim (O(n) qubits, O(n log n) layers, O(n²) CNOTs) is asserted without any explicit reversible circuit construction, gate-sequence accounting, or analysis of ancilla overhead and uncomputation costs required to replace the classical non-reversible conditional rotations and sign decisions.

    Authors: The body of the manuscript (Sections 3 and 4) supplies the explicit reversible constructions, including the handling of conditional rotations via reversible sign decisions, the uncomputation of ancillae after each iteration, and the precise CNOT and layer counts that establish the O(n), O(n log n), and O(n²) bounds. To make these claims verifiable from the abstract alone, we will add a single sentence summarizing the reversible adaptations and directing readers to the relevant sections. revision: yes

  2. Referee: [Abstract] Abstract: the statement that 'multiple approaches' exist to make CORDIC fully reversible is not accompanied by even a high-level description of how the iterative shifts, adds, and decision logic are realized reversibly while preserving the claimed asymptotics; without this, the load-bearing step from classical CORDIC to the quoted quantum costs cannot be verified.

    Authors: We agree that the abstract would benefit from a brief high-level outline of the reversible realizations. The manuscript already details two distinct approaches (one based on reversible comparison and one using controlled phase rotations) in Section 3, with the asymptotic analysis in Section 5 showing that both preserve the claimed resource bounds. In revision we will insert a short clause in the abstract describing the core reversible primitives (reversible shifts via bit-permutation networks, additions via ripple-carry or carry-lookahead, and decisions via reversible comparators) and reference the sections containing the full accounting. revision: yes

Circularity Check

0 steps flagged

No circularity; resource claims are constructive estimates from proposed reversible circuits

full rationale

The paper presents an algorithmic construction for a reversible quantum CORDIC implementation to compute arcsine. The stated asymptotic resource counts (O(n) qubits, O(n log n) layers, O(n²) CNOTs) are forward-looking estimates derived from the described circuit primitives and reversibility adaptations, not from any fitted parameters, self-definitional equations, or load-bearing self-citations. No equations or derivations in the provided text reduce the output claims to the inputs by construction. The work is self-contained as a proposal for circuit design, with the central premise being the existence of reversible equivalents rather than a tautological renaming or fit.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters, axioms, or invented entities; the work relies on standard assumptions of quantum circuit reversibility and CORDIC iteration correctness from classical literature.

pith-pipeline@v0.9.0 · 5736 in / 1040 out tokens · 18986 ms · 2026-05-23T17:57:50.057195+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Constants.lean phi_golden_ratio echoes
    ?
    echoes

    ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

    #iter← 5φ^{-mn} ▷ φ = (1 + √5)/2 ; F←[1,1,2,3,5,8,13,…] Fibonacci Sequence

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · 2 internal anchors

  1. [1]

    Quantum algorithms for shapley value calculation

    Iain Burge, Michel Barbeau, and Joaquin Garcia-Alfaro. Quantum algorithms for shapley value calculation. In 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 1, pages 1–9. IEEE, 2023

    work page 2023

  2. [2]

    Quantum cordic algorithm implementation, companion github repository, Oct

    Iain Burge, Michel Barbeau, and Joaquin Garcia-Alfaro. Quantum cordic algorithm implementation, companion github repository, Oct

    work page

  3. [3]

    https://github.com/iain-burge/QuantumCORDIC

    work page

  4. [4]

    Quantum random access memory

    Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical review letters, 100(16):160501, 2008

    work page 2008

  5. [5]

    Optimizing Quantum Circuits for Arithmetic

    Thomas H ¨aner, Martin Roetteler, and Krysta M Svore. Optimizing quantum circuits for arithmetic. arXiv preprint arXiv:1805.12445, 2018

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  6. [6]

    Quantum algorithm for linear systems of equations

    Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical review letters , 103(15):150502, 2009

    work page 2009

  7. [7]

    Computing functions cos/sup-1/and sin/sup-1/using cordic

    Christophe Mazenc, Xavier Merrheim, and J-M Muller. Computing functions cos/sup-1/and sin/sup-1/using cordic. IEEE Transactions on Computers, 42(1):118–122, 1993

    work page 1993

  8. [8]

    Quantum analog-digital conversion

    Kosuke Mitarai, Masahiro Kitagawa, and Keisuke Fujii. Quantum analog-digital conversion. Physical Review A , 99(1):012301, 2019

    work page 2019

  9. [9]

    Quantum speedup of monte carlo methods

    Ashley Montanaro. Quantum speedup of monte carlo methods. Pro- ceedings of the Royal Society A: Mathematical, Physical and Engineer- ing Sciences, 471(2181):20150301, 2015

    work page 2015

  10. [10]

    Quantum Addition Circuits and Unbounded Fan-Out

    Yasuhiro Takahashi, Seiichiro Tani, and Noboru Kunihiro. Quantum ad- dition circuits and unbounded fan-out. arXiv preprint arXiv:0910.2530, 2009

    work page internal anchor Pith review Pith/arXiv arXiv 2009

  11. [11]

    The cordic trigonometric computing technique

    Jack E V older. The cordic trigonometric computing technique. IRE Transactions on electronic computers , (3):330–334, 1959

    work page 1959

  12. [12]

    A unified algorithm for elementary functions

    John Stephen Walther. A unified algorithm for elementary functions. In Proceedings of the May 18-20, 1971, spring joint computer conference , pages 379–385, 1971

    work page 1971

  13. [13]

    Quantum circuits design for evaluating transcendental functions based on a function-value binary expansion method

    Shengbin Wang, Zhimin Wang, Wendong Li, Lixin Fan, Guolong Cui, Zhiqiang Wei, and Yongjian Gu. Quantum circuits design for evaluating transcendental functions based on a function-value binary expansion method. Quantum Information Processing , 19:1–31, 2020. APPENDIX A. MU L T FUNCTION To understand the Mult algorithm, it is most simple to considered its i...

    work page 2020