Efficient Floating Point Arithmetic for Quantum Computers

Raphael Seidel, Nikolay Tcholtchev, Sebastian Böck, Colin Kai‐Uwe Becker, Manfred Hauswirth

Abstract

One of the major promises of quantum computing is the realization of SIMD (single instruction - multiple data) operations using the phenomenon of superposition. Since the dimension of the state space grows exponentially with the number of qubits, we can easily reach situations where we pay less than a single quantum gate per data point for data-processing instructions which would be rather expensive in classical computing. Formulating such instructions in terms of quantum gates, however, still remains a challenging task. Laying out the foundational functions for more advanced data-processing is therefore a subject of paramount importance for advancing the realm of quantum computing. In this paper, we introduce the formalism of encoding so called-semi-boolean polynomials. As it turns out, arithmetic $\mathbb{Z}/2^n\mathbb{Z}$ ring operations can be formulated as semi-boolean polynomial evaluations, which allows convenient generation of unsigned integer arithmetic quantum circuits. For arithmetic evaluations, the resulting algorithm has been known as Fourier-arithmetic. We extend this type of algorithm with additional features, such as ancilla-free in-place multiplication and integer coefficient polynomial evaluation. Furthermore, we introduce a tailor-made method for encoding signed integers succeeded by an encoding for arbitrary floating-point numbers. This representation of floating-point numbers and their processing can be applied to any quantum algorithm that performs unsigned modular integer arithmetic. We discuss some further performance enhancements of the semi boolean polynomial encoder and finally supply a complexity estimation. The application of our methods to a 32-bit unsigned integer multiplication demonstrated a 90% circuit depth reduction compared to carry-ripple approaches.

TL;DR

Researchers have introduced a framework using semi-boolean polynomials to perform high-speed, parallelized floating-point arithmetic on quantum computers. By shifting arithmetic into the "Fourier domain," they achieve a 90% reduction in circuit depth for 32-bit multiplication, effectively enabling a form of quantum SIMD (Single Instruction, Multiple Data).

What Problem Does This Paper Address?

In classical computing, arithmetic is the bedrock of every application. However, translating these operations to quantum hardware is notoriously difficult. Standard classical approaches, like "carry-ripple" adders, are highly sequential; each bit depends on the previous one, leading to deep circuits that are prone to decoherence (quantum noise).

The sequential nature of classical addition algorithms, where each bit depends on the previous carry.

Furthermore, to truly harness quantum advantage, we need to perform arithmetic on superpositions of numbers—essentially processing millions of data points simultaneously. Existing quantum arithmetic often struggles with signed integers and floating-point numbers, or requires a massive number of "ancilla" (extra) qubits and complex bit-shifting logic. This paper seeks a more efficient, lower-depth way to handle these foundational operations.

Methods

The researchers build their approach on three main pillars:

  1. Semi-Boolean (SB) Polynomials: They represent arithmetic operations as multivariate polynomials where the variables are Boolean (0 or 1) but the coefficients are real numbers. They show that any integer ring operation ($\mathbb{Z}/2^n\mathbb{Z}$) can be formulated this way.
  2. Fourier-Arithmetic: Instead of computing in the standard basis, they use the Quantum Fourier Transform (QFT) to move the state into a phase-encoded representation. In this "frequency domain," addition becomes a simple sequence of phase rotations, which are inherently parallelizable.
  3. Mono-Quantum Floating-Point Encoding: To avoid the "unwieldy" logic of quantum-conditioned bit shifting, they propose a hybrid format. The mantissa (the significant digits) is stored as a quantum register, while the exponent is treated as a classically known value. This "mono-quantum" approach allows them to reuse efficient integer circuits for floating-point math.
Quantum circuit architecture for evaluating semi-boolean polynomials using the Fourier domain.

Key Insights and Ideas

  • The "Inverse Curse of Dimensionality": The authors argue that because the quantum state space grows exponentially, we can reach a point where we pay less than a single gate per data point. If you have $10^{19}$ states in superposition, one multiplication circuit processes them all at once.
  • Parallelism over Gate Count: While their method actually uses more total CNOT gates than some ripple-carry adders, the circuit depth (the number of sequential steps) is much lower. In quantum computing, depth is the primary enemy because qubits have limited "coherence time."
  • Sign Handling via Modular Rings: Rather than using a dedicated sign bit, they use modular isomorphisms. This allows signed arithmetic to "piggyback" on unsigned integer circuits without extra logic.
  • Hardware-Specific Optimization: Ion-trap architectures using Global Mølmer-Sørensen (GMS) gates are particularly well-suited for this method, as GMS gates can execute multiple entangling operations in a single laser pulse.

Key Results

  • 90% Depth Reduction: For a 32-bit unsigned integer multiplication, the SBP-encoder's circuit depth was only 10.7% of the depth required by standard ripple-carry approaches.
  • Zettascale Potential: A quantum computer with only 200 qubits could theoretically match the processing power of a zettascale ($10^{21}$ FLOPS) classical supercomputer by utilizing these high-parallelism arithmetic circuits.
  • Flexible Scaling: The introduction of "Image Extension" polynomials allows the algorithm to work across registers of different sizes without wasting resources.

Limitations and Future Work

  • Phase Precision: The method relies on very small phase rotations (RZ gates). As the number of bits increases, these phases become exponentially small, which may eventually hit the precision limits of physical hardware.
  • Gate Count Trade-off: While depth is reduced, the total number of CNOT gates is higher ($O(\log(N)^3)$ for multiplication). On hardware with high gate error rates, this could be a drawback.
  • In-place Multiplication: Purely quantum in-place multiplication for all integers remains a challenge, as it is only mathematically reversible for odd numbers without additional workarounds.
  • Future Direction: Integrating Karatsuba’s divide-and-conquer algorithm could help handle even larger operands while maintaining precision.

Summary updated

Abstract

One of the major promises of quantum computing is the realization of SIMD (single instruction - multiple data) operations using the phenomenon of superposition. Since the dimension of the state space grows exponentially with the number of qubits, we can easily reach situations where we pay less than a single quantum gate per data point for data-processing instructions which would be rather expensive in classical computing. Formulating such instructions in terms of quantum gates, however, still remains a challenging task. Laying out the foundational functions for more advanced data-processing is therefore a subject of paramount importance for advancing the realm of quantum computing. In this paper, we introduce the formalism of encoding so called-semi-boolean polynomials. As it turns out, arithmetic $\mathbb{Z}/2^n\mathbb{Z}$ ring operations can be formulated as semi-boolean polynomial evaluations, which allows convenient generation of unsigned integer arithmetic quantum circuits. For arithmetic evaluations, the resulting algorithm has been known as Fourier-arithmetic. We extend this type of algorithm with additional features, such as ancilla-free in-place multiplication and integer coefficient polynomial evaluation. Furthermore, we introduce a tailor-made method for encoding signed integers succeeded by an encoding for arbitrary floating-point numbers. This representation of floating-point numbers and their processing can be applied to any quantum algorithm that performs unsigned modular integer arithmetic. We discuss some further performance enhancements of the semi boolean polynomial encoder and finally supply a complexity estimation. The application of our methods to a 32-bit unsigned integer multiplication demonstrated a 90\% circuit depth reduction compared to carry-ripple approaches.
BibTeX
@misc{seidel2021efficient,
  author = {Raphael Seidel and Nikolay Tcholtchev and Sebastian Böck and Colin Kai‐Uwe Becker and Manfred Hauswirth},
  title = {{Efficient Floating Point Arithmetic for Quantum Computers}},
  year = {2021},
  eprint = {2112.10537},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2112.10537},
}
Figure