Quantum CORDIC -- Arcsine on a Budget

Iain Burge; Joaquin Garcia-Alfaro; Michel Barbeau

Quantum CORDIC -- Arcsine on a Budget

T0 review · 2 major / 0 minor · reviewed 2026-05-23 · grok-4.3

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

Pith's one-line read A reversible quantum CORDIC algorithm computes the arcsine function using O(n) qubits for n-bit precision.

desk verdict The paper gives a reversible quantum CORDIC for arcsine with claimed O(n) qubits, O(n log n) layers and O(n²) CNOTs, but those numbers rest on unshown circuit details. read the letter →

arxiv 2411.14434 v3 pith:M6DUERIP submitted 2024-11-02 quant-ph cs.CR

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

classification quant-phcs.CR

keywords quantumCORDICarcsinereversiblealgorithmstrigonometricfunctionsHHLalgorithmMonteCarlo

checked against Constants

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

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.

What carries the argument

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

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.

Watch

Extended reading notes

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.

Load-bearing premise

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

Editorial extensions

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.

Reading between the lines

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.

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, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The main takeaway is a reversible adaptation of classical CORDIC to compute arcsine on a quantum computer, with explicit asymptotic bounds on space, depth and CNOT count for n-bit precision. This targets a concrete need in HHL, quantum Monte Carlo and related routines, and the abstract makes a reasonable case that shift-and-add style iteration is worth preserving if it can be made reversible. The work is new in spelling out multiple reversible routes for this particular function, which prior quantum CORDIC papers do not appear to cover. It also correctly flags the non-reversible steps (sign decisions, conditional rotations) as the main obstacle and sketches ways around them. That part is useful and grounded in the classical literature. The soft spot is exactly the one the stress-test flags: whether the reversible adders, shifters and control logic, plus ancilla management and uncomputation, actually stay inside the stated O(n) qubits and O(n²) CNOTs. Classical CORDIC already does O(n) iterations on O(n)-bit numbers; each reversible primitive carries its own overhead, and without the gate sequences or a full resource table it is impossible to check if the asymptotics survive. The abstract alone does not supply that check. This paper is for people who build oracles for linear-algebra or sampling algorithms and are willing to implement or refine the circuits themselves. A reader in that group can extract the high-level idea and the application list even if they later adjust the cost model. It deserves peer review because the target primitive is relevant and the approach is concrete; the authors should expect questions on the exact gate counts and should be ready to supply the missing circuit breakdown.

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)

[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.
[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

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
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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 0 assumptions · 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.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Quantum CORDIC -- Arcsine on a Budget." pith.science (2026). https://pith.science/paper/M6DUERIP

@misc{pith2026241114434,
  author       = {Pith},
  title        = {Pith review of: Quantum CORDIC -- Arcsine on a Budget},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/M6DUERIP}},
  note         = {Machine review of arXiv:2411.14434}
}

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 an approach 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.

Figures

Figures reproduced from arXiv: 2411.14434 by the authors.

**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.** 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 times per iter… view at source ↗

**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 ↗

Discussion (0). Continue with ORCID to comment.

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.

Forward citations

Cited by 2 Pith papers

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

Fullqubit alchemist: Quantum algorithm for alchemical free energy calculations
quant-ph 2025-08 conditional novelty 6.0 of 10

A quantum algorithm for alchemical free energy calculations that block-encodes the Liouvillian to simulate molecular dynamics with polylogarithmic precision scaling, avoiding entropy estimation.
A Shapley Value Estimation Speedup for Efficient Explainable Quantum AI
quant-ph 2024-12 conditional novelty 5.0 of 10

Quantum amplitude estimation can estimate Shapley values with O(1/ε) queries to the value function, a quadratic improvement over classical Monte Carlo's O(σ²/ε²).

Pith tools

Reviewed May 23, 2026 · model on record in the stance chip above.