Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0901.3903

Resources for Measurement-Based Quantum Carry-Lookahead Adder

Agung Trisetyarso, Rodney Van Meter, Kohei M. Itoh

Published Jan 25, 2009• 2 citations
arXivHTMLPDF

Abstract

We present the design of a quantum carry-lookahead adder using measurement-based quantum computation. QCLA utilizes MBQC`s ability to transfer quantum states in unit time to accelerate addition. The quantum carry-lookahead adder (QCLA) is faster than a quantum ripple-carry adder; QCLA has logarithmic depth while ripple adders have linear depth. QCLA is an order of magnitude faster than a ripple-carry adder when adding registers longer than 100 qubits but requires a cluster state that is an order of magnitude larger. Hand optimization results in a $\approx$ 26% reduction in spatial resources for the circuit.

DOI
10.48550/arxiv.0901.3903

Related papers

CIRCUIT DESIGN FOR A MEASUREMENT-BASED QUANTUM CARRY-LOOKAHEAD ADDER

Agung Trisetyarso, Rodney Van Meter

We present the design and evaluation of a quantum carry-lookahead adder (QCLA) using measurement-based quantum computation (MBQC), called MBQCLA. QCLA was originally designed for an abstract, concurrent architecture supporting long-distance communication, but most realistic architectures heavily constrain communication distances. The quantum carry-lookahead adder is faster than a quantum ripple-carry adder; QCLA has logarithmic depth while ripple adders have linear depth. MBQCLA utilizes MBQC's ability to transfer quantum states in unit time to accelerate addition. MBQCLA breaks the latency limit of addition circuits in nearest neighbor-only architectures: compared to the Θ(n) limit on circuit depth for linear nearest-neighbor architectures, it can reach Θ(log n) depth. MBQCLA is an order of magnitude faster than a ripple-carry adder when adding registers longer than 100 qubits, but requires a cluster state that is an order of magnitude larger. The cluster state resources can be classified as computation and communication; for the unoptimized form, ≈ 88% of the resources are used for communication. Hand optimization of horizontal communication costs results in a ≈ 12% reduction in spatial resources for the in-place MBQCLA circuit. For comparison, a graph state quantum carry-lookahead adder (GSQCLA) uses only ≈ 9% of the spatial resources of the MBQCLA.

arXiv:0903.0748•International Journal of Quantum Information•Aug 1, 2010•23 citations

A Measurement-Based Form of the Out-of-Place Quantum Carry-Lookahead Adder

Agung Trisetyarso, Rodney Van Meter, Kohei M. Itoh

We present the design of a quantum carry-lookahead adder using measurement-based quantum computation. The quantum carry-lookahead adder (QCLA) is faster than a quantum ripple-carry adder; QCLA has logarithmic depth while ripple adders have linear depth. Our design is evaluated in terms of number of time steps and the total number of qubits used.

arXiv:0901.3901•Jan 25, 2009•0 citations

A Measurement-Based Form of the Out-of-Place Quantum Carry Lookhead Adder

Agung Trisetyarso, Rodney Van Meter, Kohei M. Itoh

We present the design of aquantum carry-lookahead adder using measurement-based quantum computation.The quantum carry-lookahead adder (QCLA) is faster than aquantum ripple-carry adder; QCLA has logarithmic depth while ripple adders have linear depth. Our design is evaluated in terms of number of time steps, number of measurements, the total number of qubits used and the number of successful clustering operations required. Keyword : Quantum Carry-Lookahead Adder, Cluster-State Computation

Jurnal Otomasi Kontrol dan Instrumentasi•Jan 3, 2011•0 citations

A logarithmic-depth quantum carry-lookahead adder

Thomas G. Draper, Samuel Kutin, Eric M. Rains +1 more

We present an efficient addition circuit, borrowing techniques from the classical carry-lookahead arithmetic circuit. Our quantum carry-lookahead (QCLA) adder accepts two n-bit numbers and adds them in O(log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The QCLA adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.

Quantum Information and Computation•Jul 1, 2006•146 citations

A logarithmic-depth quantum carry-lookahead adder

Draper, Thomas G., Kutin, Samuel A., Rains, Eric M. +1 more

We present an efficient addition circuit, borrowing techniques from the classical carry-lookahead arithmetic circuit. Our quantum carry-lookahead (QCLA) adder accepts two n-bit numbers and adds them in O(log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The QCLA adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.

arXiv:quant-ph/0406142•Jun 20, 2004•18 citations

A logarithmic-depth quantum carry-lookahead adder

Thomas G. Draper, Samuel Kutin, Eric M. Rains +1 more

We present an efficient addition circuit, borrowing techniques from classical carry-lookahead arithmetic. Our quantum carry-lookahead (\QCLA) adder accepts two n-bit numbers and adds them in O(\log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The \QCLA\ adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.

Quantum Information and Computation•Jul 1, 2006•101 citations
We present the design of a quantum carry-lookahead adder using measurement-based quantum computation. QCLA utilizes MBQC`s ability to transfer quantum states in unit time to accelerate addition. The quantum carry-lookahead adder (QCLA) is faster than a quantum ripple-carry adder; QCLA has logarithmic depth while ripple adders have linear depth. QCLA is an order of magnitude faster than a ripple-carry adder when adding registers longer than 100 qubits but requires a cluster state that is an order of magnitude larger. Hand optimization results in a ≈\approx≈ 26% reduction in spatial resources for the circuit.
We present the design and evaluation of a quantum carry-lookahead adder (QCLA) using measurement-based quantum computation (MBQC), called MBQCLA. QCLA was originally designed for an abstract, concurrent architecture supporting long-distance communication, but most realistic architectures heavily constrain communication distances. The quantum carry-lookahead adder is faster than a quantum ripple-carry adder; QCLA has logarithmic depth while ripple adders have linear depth. MBQCLA utilizes MBQC's ability to transfer quantum states in unit time to accelerate addition. MBQCLA breaks the latency limit of addition circuits in nearest neighbor-only architectures: compared to the Θ(n) limit on circuit depth for linear nearest-neighbor architectures, it can reach Θ(log n) depth. MBQCLA is an order of magnitude faster than a ripple-carry adder when adding registers longer than 100 qubits, but requires a cluster state that is an order of magnitude larger. The cluster state resources can be classified as computation and communication; for the unoptimized form, ≈ 88% of the resources are used for communication. Hand optimization of horizontal communication costs results in a ≈ 12% reduction in spatial resources for the in-place MBQCLA circuit. For comparison, a graph state quantum carry-lookahead adder (GSQCLA) uses only ≈ 9% of the spatial resources of the MBQCLA.
We present an efficient addition circuit, borrowing techniques from the classical carry-lookahead arithmetic circuit. Our quantum carry-lookahead (QCLA) adder accepts two n-bit numbers and adds them in O(log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The QCLA adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.
We present an efficient addition circuit, borrowing techniques from the classical carry-lookahead arithmetic circuit. Our quantum carry-lookahead (QCLA) adder accepts two n-bit numbers and adds them in O(log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The QCLA adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.
We present an efficient addition circuit, borrowing techniques from classical carry-lookahead arithmetic. Our quantum carry-lookahead (\QCLA) adder accepts two n-bit numbers and adds them in O(\log n) depth using O(n) ancillary qubits. We present both in-place and out-of-place versions, as well as versions that add modulo 2^n and modulo 2^n - 1. Previously, the linear-depth ripple-carry addition circuit has been the method of choice. Our work reduces the cost of addition dramatically with only a slight increase in the number of required qubits. The \QCLA\ adder can be used within current modular multiplication circuits to reduce substantially the run-time of Shor's algorithm.