A Higher Radix Architecture for Quantum Carry-lookahead Adder

• URL: http://arxiv.org/abs/2304.02921v2
• Date: Fri, 7 Apr 2023 06:31:06 GMT
• Title: A Higher Radix Architecture for Quantum Carry-lookahead Adder
• Authors: Siyi Wang and Anubhab Baksi and Anupam Chattopadhyay
• Abstract summary: 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.
• Score: 6.555487346177925
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In this paper, we propose an efficient quantum carry-lookahead adder based on the higher radix structure. For the addition of two $n$-bit numbers, our adder uses $O(n)-O(\frac{n}{r})$ qubits and $O(n)+O(\frac{n}{r})$ T gates to get the correct answer in T-depth $O(r)+O(\log{\frac{n}{r}})$, where $r$ is the radix. Quantum carry-lookahead adder has already attracted some attention because of its low T-depth. Our work further reduces the overall cost by introducing a higher radix layer. 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. Even compared to the Draper out-of-place adder which is very compact and efficient, our adder is still better in terms of T-count.

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)
• A note on quantum lower bounds for local search via congestion and expansion [4.68073705539907]
  We show that the quantum query complexity of local search on $G$ is $Omegabigl( fracnfrac34sqrtg bigr)$.<n>In contrast to the classical setting, a gap remains in the quantum case between our lower bound and the best-known upper bound of $Obigl( nfrac13 bigr)$ for such graphs.
  arXiv  Detail & Related papers  (2024-12-17T21:42:42Z)
• Quantum state preparation with optimal T-count [2.1386090295255333]
  We show how many T gates are needed to approximate an arbitrary $n$-qubit quantum state to within error $varepsilon$. We also show that this is the optimal T-count for implementing an arbitrary diagonal $n$-qubit unitary to within error $varepsilon$.
  arXiv  Detail & Related papers  (2024-11-07T15:29:33Z)
• A quantum random access memory (QRAM) using a polynomial encoding of binary strings [0.0]
  A quantum random access memory (QRAM) is a promising architecture for realizing quantum oracles. We develop a new design for QRAM and implement it with Clifford+T circuit. We achieve an exponential improvement in T-depth, while reducing T-count and keeping the qubit count same.
  arXiv  Detail & Related papers  (2024-08-28T18:39:56Z)
• Rank Is All You Need: Estimating the Trace of Powers of Density Matrices [1.5133368155322298]
  Estimating the trace of powers of identical $k$ density matrices is a crucial subroutine for many applications. Inspired by the Newton-Girard method, we developed an algorithm that uses only $mathcalO(r)$ qubits and $mathcalO(r)$ multi-qubit gates.
  arXiv  Detail & Related papers  (2024-08-01T06:23:52Z)
• Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
  We study the problem of underlinelow-rank matrix bandit with underlineheavy-underlinetailed underlinerewards (LowHTR) By utilizing the truncation on observed payoffs and the dynamic exploration, we propose a novel algorithm called LOTUS.
  arXiv  Detail & Related papers  (2024-04-26T21:54:31Z)
• Optimizing T and CNOT Gates in Quantum Ripple-Carry Adders and Comparators [0.0]
  The ripple-carry strategy for the addition and comparison of two n-bit numbers is presented. In particular, we consider the adders presented by Cuccaro et al. and Takahashi et al.
  arXiv  Detail & Related papers  (2024-01-31T15:34:56Z)
• Enlarging the notion of additivity of resource quantifiers [62.997667081978825]
  Given a quantum state $varrho$ and a quantifier $cal E(varrho), it is a hard task to determine $cal E(varrhootimes N)$. We show that the one shot distillable entanglement of certain spherically symmetric states can be quantitatively approximated by such an augmented additivity.
  arXiv  Detail & Related papers  (2022-07-31T00:23:10Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  We introduce a batch algorithm inspired by finite-arm bandit algorithms. We show that it achieves the cumulative regret upper bound $Oast(sqrtTgamma_T)$ using $O(loglog T)$ batches within time horizon $T$. In addition, we propose a modified version of our algorithm, and characterize how the regret is impacted by the number of batches.
  arXiv  Detail & Related papers  (2021-10-15T00:54:04Z)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  We study efficient estimation and detection of a planted vector $v$ whose $ell_4$ norm differs from that of a Gaussian vector with the same $ell$ norm. We show that in the regime $n rho gg sqrtN$, any spectral method from a large class (and more generally, any low-degree of the input) fails to detect the planted vector.
  arXiv  Detail & Related papers  (2021-05-31T16:10:49Z)
• Adder Neural Networks [75.54239599016535]
  We present adder networks (AdderNets) to trade massive multiplications in deep neural networks. In AdderNets, we take the $ell_p$-norm distance between filters and input feature as the output response. We show that the proposed AdderNets can achieve 75.7% Top-1 accuracy 92.3% Top-5 accuracy using ResNet-50 on the ImageNet dataset.
  arXiv  Detail & Related papers  (2021-05-29T04:02:51Z)
• 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)
• Quantum block lookahead adders and the wait for magic states [0.0]
  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.
  arXiv  Detail & Related papers  (2020-12-03T01:15:43Z)
• Thresholded Lasso Bandit [70.17389393497125]
  Thresholded Lasso bandit is an algorithm that estimates the vector defining the reward function as well as its sparse support. We establish non-asymptotic regret upper bounds scaling as $mathcalO( log d + sqrtT )$ in general, and as $mathcalO( log d + sqrtT )$ under the so-called margin condition.
  arXiv  Detail & Related papers  (2020-10-22T19:14:37Z)
• 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)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  Solving optimal transport with an entropic regularization requires computing a $ntimes n$ kernel matrix that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-logdotpvarphi(x)varphi(y)$ where $varphi$ is a map from the ground space onto the positive orthant $RRr_+$, with $rll n$.
  arXiv  Detail & Related papers  (2020-06-12T10:21:40Z)

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.