Related papers: Prefix Sums via Kronecker Products

Prefix Sums via Kronecker Products

URL: http://arxiv.org/abs/2512.16309v2
Date: Tue, 23 Dec 2025 14:48:36 GMT
Title: Prefix Sums via Kronecker Products
Authors: Aleksandros Sobczyk, Anastasios Zouzias,
Abstract summary: We show how to design quantum adders with $1.893log(n)+O(1)$ Toffoli depth, $O(n)$ Toffoli gates, and $O(n)$ additional qubits.<n>As an application, we show how to use these circuits to design quantum adders with $1.893log(n)+O(1)$ Toffoli depth, $O(n)$ Toffoli gates, and $O(n)$ additional qubits.
Score: 47.600794349481966
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: In this work, we revisit prefix sums through the lens of linear algebra. We describe an identity that decomposes triangular all-ones matrices as a sum of two Kronecker products, and apply it to design recursive prefix sum algorithms and circuits. Notably, the proposed family of circuits is the first one that achieves the following three properties simultaneously: (i) zero-deficiency, (ii) constant fan-out per-level, and (iii) depth that is asymptotically strictly smaller than $2\log(n)$ for input length $n$. As an application, we show how to use these circuits to design quantum adders with $1.893\log(n)+O(1)$ Toffoli depth, $O(n)$ Toffoli gates, and $O(n)$ additional qubits, improving the Toffoli depth and/or Toffoli size of existing constructions.

Related papers

Stesso: A reconfigurable decomposition of $n$-bit Toffoli gates using symmetrical logical structures and adjustable support qubits [2.349579657464914]
This paper introduces a new structural design method to effectively decompose $(n+1)$-bit Toffoli gates by utilizing ancilla qubits.<n>It has been experimentally proven that $(n+1)$-bit Toffoli gates always have lower quantum costs than using conventional composition methods.
arXiv Detail & Related papers (2025-10-30T03:58:02Z)
The Generative Leap: Sharp Sample Complexity for Efficiently Learning Gaussian Multi-Index Models [71.5283441529015]
In this work we consider generic Gaussian Multi-index models, in which the labels only depend on the (Gaussian) $d$-dimensional inputs through their projection onto a low-dimensional $r = O_d(1)$ subspace.<n>We introduce the generative leap exponent $kstar$, a natural extension of the generative exponent from [Damian et al.'24] to the multi-index setting.
arXiv Detail & Related papers (2025-06-05T18:34:56Z)
Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA [45.810803542748495]
Windowed arithmetic is a technique for reducing the cost of quantum circuits with space--time tradeoffs.<n>In this work we introduce four optimizations to windowed modular exponentiation.<n>This leads to a $3%$ improvement in Toffoli count and Toffoli depth for modular exponentiation circuits relevant to cryptographic applications.
arXiv Detail & Related papers (2025-02-24T16:59:16Z)
Ancilla-free Quantum Adder with Sublinear Depth [2.784223169208082]
We present the first exact quantum adder with sublinear depth and no ancilla qubits.<n>Our construction is based on classical reversible logic only.<n>We also present new constructions for incrementing and adding a constant to a quantum register.
arXiv Detail & Related papers (2025-01-28T09:05:49Z)
Quantum binary field multiplication with subquadratic Toffoli gate count and low space-time cost [3.129187821625805]
We present an algorithm for constructing quantum circuits that perform multiplication over $GF (2n)$ with $mathcalO(nlog_(n))bits.<n>For some primitives, such as trinomials, the multiplication can be done in logarithmic depth and with $mathcalO(nlog_(n))bits.
arXiv Detail & Related papers (2025-01-27T15:26:11Z)
Overcomplete Tensor Decomposition via Koszul-Young Flattenings [56.82556231289414]
We give a new algorithm for decomposing an $n_times n times n_3$ tensor as the sum of a minimal number of rank-1 terms.<n>We show that an even more general class of degree-$d$s cannot surpass rank $Cn$ for a constant $C = C(d)$.
arXiv Detail & Related papers (2024-11-21T17:41:09Z)
Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an $(N-1)times (N-1)$ matrix.<n>The basic idea is to encode each row of the matrix into a pure state of some quantum system.
arXiv Detail & Related papers (2024-01-29T23:23:27Z)
Polylogarithmic-depth controlled-NOT gates without ancilla qubits [0.0]
Controlled operations are fundamental building blocks of quantum algorithms. Decomposing $n$-control-NOT gates into arbitrary single-qubit and CNOT gates is a crucial but non-trivial task.
arXiv Detail & Related papers (2023-12-20T17:23:11Z)
Improved Synthesis of Toffoli-Hadamard Circuits [1.7205106391379026]
We show that a technique introduced by Kliuchnikov in 2013 for Clifford+$T$ circuits can be straightforwardly adapted to Toffoli-Hadamard circuits. We also present an alternative synthesis method of similarly improved cost, but whose application is restricted to circuits on no more than three qubits.
arXiv Detail & Related papers (2023-05-18T21:02:20Z)
Quantum Fourier Addition, Simplified to Toffoli Addition [92.18777020401484]
We present the first systematic translation of the QFT-addition circuit into a Toffoli-based adder. Instead of using approximate decompositions of the gates from the QFT circuit, it is more efficient to merge gates.
arXiv Detail & Related papers (2022-09-30T02:36:42Z)
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)

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