CoChat
Sign Up
PreprintCited by 3Quantum Computing Algorithms and ArchitectureCryptography and Residue ArithmeticQuantum Information and Cryptography

Approximate encoded permutations and piecewise quantum adders

Open access
Gidney, Craig·2019·arXiv
DOI 10.48550/arxiv.1905.08488arXiv 1905.08488
Open this paper in CoChat — free accountOpen PDF

Abstract

We present a paradigm for constructing approximate quantum circuits from reversible classical circuits that operate on many possible encodings of an input and send almost all encodings of that input to an encoding of the correct output. We introduce oblivious carry runways, which use piecewise addition circuits to perform approximate encoded additions and reduce the asymptotic depth of addition to $O(\lg \lg n)$. We show that the coset representation of modular integers (Zalka 2006) is an approximate encoded modular addition, and that it can be used in combination with oblivious carry runways. We prove error bounds on these approximate representations, and use them to construct 2s-complement adders and modular adders with lower costs than in previous work at register sizes relevant in practice.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1905.08488

Cites

2 of 2 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • A controlled non-modular addition can be performed in 4n Toffolis, significantly cheaper than the 10n assumed for a controlled modular adder.

    “It is possible to perform a controlled non-modular addition in 4 n Toffolis [18, 32], significantly cheaper than the 10 n we assumed for a controlled modular adder.”

    From How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits (2021) · cites this paper as [32]

    Section 5 (p. 11) gives a Toffoli count for piecewise additions, but does not specify a controlled non-modular adder costing 4n Toffolis. Searches for controlled addition and 4n found no passage establishing that cost. The 10n figure is explicitly the citing authors’ own assumption, not a figure attributed to this source. (LLM, conf=0.72)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 8

  1. [1][1] Daniel J Bernstein. Curve25519: new diffie-hellman speed records. In International Workshop on Public Key Cryptography , pages 207-228. Springer, 2006. -
  2. [2][2] Steven A Cuccaro, Thomas G Draper, Samuel A Kutin, and David Petrie Moulton. A new quantum ripple-carry addition circuit. arXiv preprint quant-ph/0410184 , 2004. - · arXiv
  3. [3][3] Thomas G Draper, Samuel A Kutin, Eric M Rains, and Krysta M Svore. A logarithmic-depth quantum carry-lookahead adder. arXiv preprint quant-ph/0406142 , 2004. - · arXiv
  4. [4][4] Austin G Fowler. Time-optimal quantum computation. arXiv preprint arXiv:1210.4626 , 2012. - · arXiv
  5. [6][6] Craig Gidney. Efficient magic state factories with a catalyzed | CCZ 〉 to 2 | T 〉 transformation. Quantum , 3, April 2019. DOI: 10.22331/q-2019-04-30-135. - · DOI · Paper page
  6. [7][7] Craig Gidney. Asymptotically efficient quantum karatsuba multiplication. arXiv preprint arXiv:1904.07356 , 2019. - · arXiv
  7. [8][8] Torbj¨ orn Granlund and the GMP development team. The gnu multiple precision arithmetic library, edition 5.1.1, section 8.1 nails. https://gmplib.org/gmp-man-5.1.1.pdf , 2013. Accessed: 2019-05-02. -
  8. [10][10] Christof Zalka. Shor's algorithm with fewer (pure) qubits. arXiv preprint quant-ph/0601097 , 2006. · arXiv

Cited by

Sorted by citations

Authors
Gidney, C.
Affiliations
Google (United States) (US)
Corresponding author
Gidney, Craig
Venue
arXiv
Publisher
arXiv
Published
2019
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1905.08488
arXiv
1905.08488
OpenAlex
W2946645353
Cited by
3
References
2
Citations by year
2022: 1 · 2020: 1 · 2019: 1
Type
posted content
Language
en
Open access
Licence
creativecommons.org/licenses/by/4.0/legalcode
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University) (cc-by)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
Keywords
modular adders, circuit depth reduction, error bounds

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review