Quantum CORDIC -- Arcsine on a Budget

✨

This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a quantum computer, but you are working with a very strict budget. You don't have fancy, expensive tools like heavy-duty multipliers or massive memory banks. You only have the basics: the ability to shift bits (like moving beads on an abacus) and add them together.

This paper introduces a clever way to solve a very difficult math problem—calculating the arcsine function (which is essentially finding an angle when you know the height of a triangle)—using only those basic, low-cost tools.

Here is the breakdown of their solution using everyday analogies:

1. The Problem: The "Expensive" Math

In the world of quantum computing, many powerful algorithms (like solving complex equations or simulating random events) need to turn a simple number (like "0.5") into a specific probability (like "there is a 70% chance of this happening"). To do this, the computer needs to calculate an arcsine.

Usually, doing this math on a quantum computer is like trying to bake a cake in a kitchen that only has a hammer and a spoon. It requires complex, expensive operations that current quantum computers can't easily handle.

2. The Old Solution: The "CORDIC" Compass

The authors borrow a trick from the 1950s called CORDIC (COordinate Rotation DIgital Computer).

The Analogy: Imagine you are standing in a field facing North, and you want to face a specific direction (say, 30 degrees East). You don't have a protractor. Instead, you have a list of tiny steps you can take: "Turn a little bit right," "Turn a tiny bit more right," "Turn a tiny, tiny bit right."
How it works: You keep taking these pre-calculated, tiny steps until you are pointing in the right direction. You don't need to do complex multiplication; you just need to add and subtract small numbers. This was a lifesaver for early, weak computers, and the authors realized it could be a lifesaver for today's "weak" quantum computers too.

3. The Hurdle: The Quantum "No-Deleting" Rule

There is a catch. Quantum computers follow a strict rule: You cannot delete information. In the old 1950s version of CORDIC, the computer would calculate a step, use the result, and then throw the old numbers away to save space.

In the quantum world, throwing numbers away is like trying to un-burn a piece of paper; it breaks the laws of physics for quantum machines. The algorithm must be reversible, meaning you must be able to run the steps backward to get your original numbers back.

4. The Innovation: The "Reversible" CORDIC

The authors figured out how to make the CORDIC "compass" work without breaking the "no-deleting" rule.

The Trick: Instead of just calculating the angle and forgetting the intermediate steps, they built a system that keeps a "trail of breadcrumbs." They use a special method to multiply numbers by shifting bits (which is cheap and easy) and carefully track every move so that, once the angle is found, they can retrace their steps to clean up the mess and return the computer to a pristine state.
The Result: They created a quantum circuit that calculates the arcsine using only additions and bit-shifts. It uses a number of quantum bits (qubits) that grows linearly with the precision you want (if you want 10 bits of accuracy, you need about 10 qubits, not millions).

5. Why This Matters (The "Digital-to-Amplitude" Magic)

The paper shows how to use this new tool to perform a "Quantum Digital-to-Analog" conversion.

The Analogy: Imagine you have a digital switch that is either ON or OFF. You want to turn it into a dimmer switch where the brightness represents a probability.
The Application: By using their new CORDIC method, they can take a digital number (like a binary code) and smoothly turn it into a "dimmer" setting (a probability amplitude) without needing expensive hardware.

Summary of Claims

The paper claims to have:

Adapted an old, efficient algorithm (CORDIC) for the strict rules of quantum computing.
Solved the problem of making it "reversible" so it doesn't break quantum laws.
Demonstrated that this method is efficient, requiring:
- Space: A number of qubits proportional to the precision (linear).
- Time: A number of steps proportional to the precision times the log of the precision.
- Operations: A number of connections (CNOTs) proportional to the square of the precision.
Proven via simulation that this method works and can be used as a building block for famous quantum algorithms like HHL (solving linear equations), Monte Carlo methods (simulating randomness), and Shapley value estimation (fairly dividing credit in a group).

In short, they found a way to do complex quantum math using a "budget" toolkit, making powerful algorithms accessible to the early, limited hardware we have today.

1. Problem Statement

The paper addresses the computational challenge of efficiently calculating the arcsine function ( $\arcsin$ ) within a quantum computing context with arbitrary accuracy. This function is a critical prerequisite for several foundational quantum algorithms, including:

Harrow–Hassidim–Lloyd (HHL) algorithm: For solving linear systems of equations.
Quantum Digital-to-Analog Conversion (QDAC): Converting binary strings into probability amplitudes (e.g., $|x\rangle \to \sqrt{1-\Phi(x)}|0\rangle + \sqrt{\Phi(x)}|1\rangle$ ).
Quantum Monte Carlo methods: For speeding up stochastic simulations.
Shapley value estimation: For fair allocation in cooperative game theory.

Existing quantum approaches for inverse trigonometric functions often rely on piecewise polynomial approximations or iterative binary searches. These methods typically require significant resources, such as memory access (qRAM), complex multiplication, or square-root operations, making them difficult to implement on near-term, resource-constrained ("budget") quantum hardware.

2. Methodology

The authors propose adapting the COordinate Rotation DIgital Computer (CORDIC) algorithm, a classical iterative technique from the 1950s designed for weak hardware, to the quantum domain.

Core Challenges & Solutions

The primary challenge in quantum CORDIC is reversibility. Classical CORDIC uses non-reversible operations (like conditional swaps and overwriting variables) that destroy quantum information. The authors detail a method to make every step reversible:

Fixed-Point Representation: All variables ( $\theta, x, y, t$ ) are represented as fixed-point two's complement numbers. This avoids overflow issues and allows the use of simple bit-shifts for multiplication by powers of 2.
Reversible Logic Gates:
- Sign Detection: The algorithm determines rotation direction based on sign bits. This is implemented using Toffoli and CNOT gates to compute the control bit $d_i$ without destroying the input state.
- Pseudo-Rotation: The core rotation step involves $x' = x - 2^{-i}y$ and $y' = y + 2^{-i}x$ . Since quantum computers cannot perform arbitrary multiplication efficiently, the authors use a specialized reversible multiplication algorithm (Algorithm 2) based on Fibonacci sequences to approximate multiplication by $(1 + 2^{-k})$ using only additions and bit-shifts.
- Uncomputation: To maintain reversibility, the algorithm computes the result, applies the necessary transformations, and then reverses the auxiliary calculations (uncomputing) to return ancillary registers to the $|0\rangle$ state, leaving only the desired result.

The Quantum CORDIC Process

The algorithm iteratively rotates a vector $(x, y)$ toward a target vector defined by the input $t$ .

Initialization: Input $t$ is mapped to a vector.
Iteration: For $n$ $n$ iterations (where $n$ $n$ is the precision bits):
1. Determine rotation direction ( $d_i$ ) based on the sign of $t - y$ .
2. Conditionally swap $x$ and $y$ .
3. Perform pseudo-rotation (addition/subtraction with bit-shifts).
4. Unswap if necessary.
5. Compensate for the vector stretch caused by pseudo-rotation by scaling the target $t$ .
6. Accumulate the angle $\theta$ by adding precomputed $\arctan(2^{-i})$ terms.
Output: The accumulated angle $\theta$ approximates $\arcsin(t)$ .

3. Key Contributions

First Reversible Quantum CORDIC for Arcsine: The paper provides the first detailed construction of a fully reversible quantum circuit for computing $\arcsin$ using the CORDIC architecture.
Resource-Efficient Design: The method avoids expensive operations like full multiplication or square roots, relying instead on bit-shifts and additions, which are native to quantum hardware.
Algorithmic Adaptation: The authors successfully translated the classical CORDIC logic (specifically the Mazenc et al. variant) into a quantum circuit, solving the non-reversibility of conditional swaps and iterative updates.
Application to QDAC: They demonstrate a complete workflow for Quantum Digital-to-Amplitude conversion, showing how to encode a binary value $h_k$ into the probability amplitude $\sqrt{h_k}$ of a qubit using the quantum CORDIC primitive.

4. Results and Complexity Analysis

The authors provide theoretical complexity bounds and simulation results (using Qiskit and classical simulators).

Space Complexity: $O(n)$ $O (n)$ qubits.
- Requires approximately $5n - 1$ qubits for $n$ bits of precision (registers for $x, y, t, d$ , and an auxiliary register for multiplication).
Time/Depth Complexity: $O(n \log n)$ $O (n lo g n)$ layers.
- The circuit depth is dominated by the addition operations required for the reversible multiplication steps.
Gate Count (CNOT): $O(n^2)$ $O (n^{2})$ .
- The number of CNOT gates scales quadratically with the number of precision bits.
Accuracy:
- Simulations for $n=4, 5, 6$ (quantum) and up to $n=16$ (classical) show that the error decreases as $n$ increases.
- The error is of order $O(2^{-n})$ , allowing for arbitrary accuracy by increasing $n$ .
Performance: The method is shown to be highly effective for low-to-medium precision applications, which are the most relevant for early fault-tolerant quantum hardware.

5. Significance

This work is significant for several reasons:

Enabling Foundational Algorithms: By providing an efficient, low-resource method for calculating $\arcsin$ , the paper removes a major bottleneck for the HHL algorithm, quantum Monte Carlo simulations, and Shapley value estimation.
Hardware Compatibility: The "budget" approach (using only shifts and adds) is ideally suited for early fault-tolerant quantum computers where gate counts and qubit coherence times are limited. It avoids the heavy overhead of qRAM or complex arithmetic units.
Modularity: The proposed CORDIC module can be extended to compute other elementary functions (hyperbolic, logarithmic, exponential) within the same circuit architecture, potentially becoming a standard building block for quantum arithmetic.
Practicality: The paper bridges the gap between classical embedded computing techniques (CORDIC) and modern quantum algorithm design, proving that "old" efficient algorithms can be revitalized for the quantum era.

In conclusion, the paper presents a viable, resource-conscious pathway to implementing essential trigonometric functions on quantum hardware, directly facilitating the practical deployment of several high-impact quantum algorithms.