Quantum block lookahead adders and the wait for magic states

• URL: http://arxiv.org/abs/2012.01624v1
• Date: Thu, 3 Dec 2020 01:15:43 GMT
• Title: Quantum block lookahead adders and the wait for magic states
• Authors: Craig Gidney
• Abstract summary: We present a block lookahead adder that parallelizes across blocks of bits of size $b$, instead of over all bits. We estimate the spacetime volume of these adders, and adders from previous work, for various register sizes and factory counts under plausible assumptions for a large scale quantum computer based on the surface code and superconducting qubits.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We improve the Toffoli count of low depth quantum adders, and analyze how their spacetime cost reacts to having a limited number of magic state factories. We present a block lookahead adder that parallelizes across blocks of bits of size $b$, instead of over all bits. The block lookahead adder achieves a Toffoli count of $3n + 5n/b$ for out of place addition (vs $4n$ in previous work by Thapliyal et al) and $5n + 8n/b$ for in place addition (vs $7n$ in previous work by Thapliyal et al). The tradeoff is that the reaction depth of these circuits depends linearly on $b$, and they use additional workspace. We estimate the spacetime volume of these adders, and adders from previous work, for various register sizes and factory counts under plausible assumptions for a large scale quantum computer based on the surface code and superconducting qubits.

Related papers

• A Classical-Quantum Adder with Constant Workspace and Linear Gates [0.03922370499388702]
  I construct an adder that uses 3 clean ancillae and $4n pm O(1)$ Toffoli gates to add a classical offset into a quantum register.<n>I show that applying the presented adders conditioned on a control qubit requires no additional workspace or Toffolis.
  arXiv  Detail & Related papers  (2025-07-30T20:24:03Z)
• Ancilla-free Quantum Adder with Sublinear Depth [2.784223169208082]
  We present the first exact quantum adder with sublinear depth and no ancilla qubits. Our construction is based on classical reversible logic only.
  arXiv  Detail & Related papers  (2025-01-28T09:05:49Z)
• GPU-accelerated Effective Hamiltonian Calculator [70.12254823574538]
  We present numerical techniques inspired by Nonperturbative Analytical Diagonalization (NPAD) and the Magnus expansion for the efficient calculation of effective Hamiltonians. Our numerical techniques are available as an open-source Python package, $rm qCH_eff$.
  arXiv  Detail & Related papers  (2024-11-15T06:33:40Z)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPs were introduced by Macchi as a model in quantum optics the 1970s. Most applications require sampling from a DPP, and given their quantum origin, it is natural to wonder whether sampling a DPP on a classical computer is easier than on a classical one. Vanilla sampling consists in two steps, of respective costs $mathcalO(N3)$ and $mathcalO(Nr2)$ operations on a classical computer, where $r$ is the rank of the kernel matrix.
  arXiv  Detail & Related papers  (2023-05-25T08:43:11Z)
• A Higher Radix Architecture for Quantum Carry-lookahead Adder [6.555487346177925]
  We propose an efficient quantum carry-lookahead adder based on the higher radix structure. By analyzing the performance in T-depth, T-count, and qubit count, it is shown that the proposed adder is superior to existing quantum carry-lookahead adders.
  arXiv  Detail & Related papers  (2023-04-06T08:15:02Z)
• Does qubit connectivity impact quantum circuit complexity? [5.908927557774895]
  Some physical implementation schemes of quantum computing can apply two-qubit gates only on certain pairs of qubits. In this paper, we show that all $n$-qubit unitary operations can be implemented by quantum circuits of $O(4n)$ depth and $O(4n)$ size.
  arXiv  Detail & Related papers  (2022-11-10T08:38:29Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Truncated phase-based quantum arithmetic: error propagation and resource reduction [0.0]
  We present a modification of the Draper quantum Fourier adder which eliminates small-angle rotations to highly coarse levels. We show that the inherited loss of fidelity is directly given by the rate of carry and borrow bits in the subroutine. Surprisingly, we find that each of the $7times 107$ quantum Fourier transforms may be truncated down to $pi/64$, with additive rotations left only slightly finer.
  arXiv  Detail & Related papers  (2021-10-01T05:19:03Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• 1$\times$N Block Pattern for Network Sparsity [90.43191747596491]
  We propose one novel concept of $1times N$ block sparsity pattern (block pruning) to break this limitation. Our pattern obtains about 3.0% improvements over filter pruning in the top-1 accuracy of MobileNet-V2. It also obtains 56.04ms inference savings on Cortex-A7 CPU over weight pruning.
  arXiv  Detail & Related papers  (2021-05-31T05:50:33Z)
• Halving the width of Toffoli based constant modular addition to n+3 qubits [69.43216268165402]
  We present an arithmetic circuit performing constant modular addition having $mathcalO(n)$ depth of Toffoli gates. This is an improvement by a factor of two compared to the width of the state-of-the-art Toffoli-based constant modular adder.
  arXiv  Detail & Related papers  (2021-02-06T17:07:48Z)
• Efficient Construction of a Control Modular Adder on a Carry-Lookahead Adder Using Relative-phase Toffoli Gates [0.9697877942346909]
  We construct an efficient control modular adder with small KQ by using relative-phase Toffoli gates in two major types of quantum computers. In FTQ, $T$ gates incur heavy cost due to distillation, which fabricates ancilla for running $T$ gates with high accuracy but consumes a lot of specially prepared ancilla qubits. We propose a new control modular adder that uses only 20% of the number of $T$ gates of the original.
  arXiv  Detail & Related papers  (2020-10-01T08:55:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.