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:2211.05217 · Society for Industrial and Applied Mathematics eBooks

Smaller Low-Depth Circuits for Kronecker Powers

Josh Alman, Yunfeng Guan, Ashwin Padaki

Published Jan 1, 2023• 1 citation
arXivHTMLPDF

Abstract

A linear circuit for computing an N × N matrix M is a circuit with N inputs corresponding to the entries of a vector x and N outputs corresponding to the entries of the transformed vector Mx, and where each gate computes a linear combination of its inputs. Each gate may have unbounded fan-in, and the size of the circuit is the number of wires. This model captures most known algorithms for computing linear transforms, and (in the constant-depth or 'synchronous' settings) is equivalent to factoring M as the product of sparse matrices. We give new, smaller constructions of constant-depth linear circuits for computing any matrix which is the Kronecker power of a fixed matrix. A standard argument (e.g., the mixed product property of Kronecker products, or a generalization of the Fast Walsh-Hadamard transform) shows that any such N × N matrix has a depth-2 circuit of size O(N1.5). We improve on this for all such matrices, and especially for some such matrices of particular interest: • For any integer q > 1 and any matrix which is the Kronecker power of a fixed q × q matrix, we construct a depth-2 circuit of size O(N1.5-aq), where aq > 0 is a positive constant depending only on q. No bound beating size O(N1.5) was previously known for any q > 2. • For the case q = 2, i.e., for any matrix which is the Kronecker power of a fixed 2 × 2 matrix, we construct a depth-2 circuit of size O(N1.446), improving the prior best size O(N1.493) [Alman, 2021]. • For the Walsh-Hadamard transform, we construct a depth-2 circuit of size O(N1.443), improving the prior best size O(N1.476) [Alman, 2021]. • For the disjointness matrix (the communication matrix of set disjointness, or equivalently, the matrix for the linear transform that evaluates a multilinear polynomial on all 0/1 inputs), we construct a depth-2 circuit of size O(N1.258), improving the prior best size O(N1.272) [Jukna and Sergeev, 2013]. Our constructions also generalize to improving the standard construction for any depth ≤ O (log N). Our main technical tool is an improved way to convert a nontrivial circuit for any matrix into a circuit for its Kronecker powers. Our new bounds provably could not be achieved using the approaches of prior work.

DOI
10.1137/1.9781611977554.ch160

Related papers

Prefix Sums via Kronecker Products

Aleksandros Sobczyk, Anastasios Zouzias

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.

quant-pharXiv:2512.16309•Dec 19, 2025•0 citations

Kronecker products, low-depth circuits, and matrix rigidity

Josh Alman

For a matrix M and a positive integer r, the rank r rigidity of M is the smallest number of entries of M which one must change to make its rank at most r. There are many known applications of rigidity lower bounds to a variety of areas in complexity theory, but fewer known applications of rigidity upper bounds. In this paper, we use rigidity upper bounds to prove new upper bounds in a few different models of computation. Our results include:

ACM Symposium on Theory of Computing (STOC)•Jun 15, 2021•8 citations

The power of constant-depth quantum circuits of unbounded size

Sergii Strelchuk, Sathyawageeswar Subramanian, Máté Weisz

Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth. We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential. The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy. Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension $d$ and $M\geq d^2-1$ ports, we construct a unitary circuit of depth $O(\sqrt d)$, independent of $M$ and including resource preparation and port selection, with entanglement fidelity at least $(1-(d^2-1)/(2M))^2$. Thus, at fixed $d$, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on $d$ can also be removed remains open.

quant-pharXiv:2609.40294•Oct 1, 2026•0 citations

Quantum Circuits with Unbounded Fan-out

Peter Høyer, Robert Špalek

Abstract. We demonstrate that the unbounded fan-out gate is very powerful. Constant-depth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by QNC 0 f) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[q], and counting. Classically, we need logarithmic depth even if we can use unbounded fan-in gates. If we allow arbitrary one-qubit gates instead of a fixed basis, then these circuits can also be made exact in log-star depth. Sorting, arithmetical operations, phase estimation, and the quantum Fourier transform can also be approximated in constant depth. 1

•Jan 1, 2002•0 citations

Quantum Circuit Implementation of Two Matrix Product Operations and Elementary Column Transformations

Yu-Hang Liu, Yuan-Hong Tao, Jing-Run Lan +1 more

This paper focuses on quantum algorithms for three key matrix operations: Hadamard (Schur) product, Kronecker (tensor) product, and elementary column transformations each. By designing specific unitary transformations and auxiliary quantum measurement, efficient quantum schemes with circuit diagrams are proposed. Their computational depths are: O(1) for Kronecker product; O(max(m,n)) for Hadamard product (linked to matrix dimensions); and O(m) for elementary column transformations of (2^n X 2^m) matrices (dependent only on column count).Notably, compared to traditional column transformation via matrix transposition and row transformations, this scheme reduces computation steps and quantum gate usage, lowering quantum computing energy costs.

quant-pharXiv:2511.02413•Nov 5, 2025•0 citations

All Unitaries Have Constant Depth Quantum Circuits

Barak Nehoran, Joseph Slote, Henry Yuen

It is well-known that every $n$-qubit unitary can be implemented by a $2^{O(n)}$-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is *necessary* for general unitaries, even when allowing an unlimited number of ancilla qubits. Here we show, perhaps surprisingly, that all unitaries can be implemented exactly by a circuit of one- and two-qubit gates of depth $\mathsf{poly}(n)$ with $2^{O(n)}$ ancilla qubits. In other words, every $n$-qubit unitary can be parallelized to polynomial depth. In fact, our depth bound is *linear* in $n$, which is the best possible, and an exponential improvement on the previous best bound of $2^{n/2}$ due to Rosenthal [TQC 2022, Quantum 2026]. Moreover, if we allow unbounded fan-out gates, these circuits can be further reduced to *constant* depth. Our construction takes advantage of a novel relationship connecting the unitary synthesis problem of Aaronson and Kuperberg to locally-decodable codes and private information retrieval from complexity theory and cryptography, and has a natural interpretation in bosonic quantum computation.

quant-pharXiv:2609.40351•Oct 1, 2026•0 citations
A linear circuit for computing an N × N matrix M is a circuit with N inputs corresponding to the entries of a vector x and N outputs corresponding to the entries of the transformed vector Mx, and where each gate computes a linear combination of its inputs. Each gate may have unbounded fan-in, and the size of the circuit is the number of wires. This model captures most known algorithms for computing linear transforms, and (in the constant-depth or 'synchronous' settings) is equivalent to factoring M as the product of sparse matrices. We give new, smaller constructions of constant-depth linear circuits for computing any matrix which is the Kronecker power of a fixed matrix. A standard argument (e.g., the mixed product property of Kronecker products, or a generalization of the Fast Walsh-Hadamard transform) shows that any such N × N matrix has a depth-2 circuit of size O(N1.5). We improve on this for all such matrices, and especially for some such matrices of particular interest: • For any integer q > 1 and any matrix which is the Kronecker power of a fixed q × q matrix, we construct a depth-2 circuit of size O(N1.5-aq), where aq > 0 is a positive constant depending only on q. No bound beating size O(N1.5) was previously known for any q > 2. • For the case q = 2, i.e., for any matrix which is the Kronecker power of a fixed 2 × 2 matrix, we construct a depth-2 circuit of size O(N1.446), improving the prior best size O(N1.493) [Alman, 2021]. • For the Walsh-Hadamard transform, we construct a depth-2 circuit of size O(N1.443), improving the prior best size O(N1.476) [Alman, 2021]. • For the disjointness matrix (the communication matrix of set disjointness, or equivalently, the matrix for the linear transform that evaluates a multilinear polynomial on all 0/1 inputs), we construct a depth-2 circuit of size O(N1.258), improving the prior best size O(N1.272) [Jukna and Sergeev, 2013]. Our constructions also generalize to improving the standard construction for any depth ≤ O (log N). Our main technical tool is an improved way to convert a nontrivial circuit for any matrix into a circuit for its Kronecker powers. Our new bounds provably could not be achieved using the approaches of prior work.
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 2log⁡(n)2\log(n)2log(n) for input length nnn. As an application, we show how to use these circuits to design quantum adders with 1.893log⁡(n)+O(1)1.893\log(n)+O(1)1.893log(n)+O(1) Toffoli depth, O(n)O(n)O(n) Toffoli gates, and O(n)O(n)O(n) additional qubits, improving the Toffoli depth and/or Toffoli size of existing constructions.
Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth. We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential. The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy. Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension ddd and M≥d2−1M\geq d^2-1M≥d2−1 ports, we construct a unitary circuit of depth O(d)O(\sqrt d)O(d​), independent of MMM and including resource preparation and port selection, with entanglement fidelity at least (1−(d2−1)/(2M))2(1-(d^2-1)/(2M))^2(1−(d2−1)/(2M))2. Thus, at fixed ddd, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on ddd can also be removed remains open.
Abstract. We demonstrate that the unbounded fan-out gate is very powerful. Constant-depth polynomial-size quantum circuits with bounded fan-in and unbounded fan-out over a fixed basis (denoted by QNC 0 f) can approximate with polynomially small error the following gates: parity, mod[q], And, Or, majority, threshold[t], exact[q], and counting. Classically, we need logarithmic depth even if we can use unbounded fan-in gates. If we allow arbitrary one-qubit gates instead of a fixed basis, then these circuits can also be made exact in log-star depth. Sorting, arithmetical operations, phase estimation, and the quantum Fourier transform can also be approximated in constant depth. 1
This paper focuses on quantum algorithms for three key matrix operations: Hadamard (Schur) product, Kronecker (tensor) product, and elementary column transformations each. By designing specific unitary transformations and auxiliary quantum measurement, efficient quantum schemes with circuit diagrams are proposed. Their computational depths are: O(1) for Kronecker product; O(max(m,n)) for Hadamard product (linked to matrix dimensions); and O(m) for elementary column transformations of (2^n X 2^m) matrices (dependent only on column count).Notably, compared to traditional column transformation via matrix transposition and row transformations, this scheme reduces computation steps and quantum gate usage, lowering quantum computing energy costs.
It is well-known that every nnn-qubit unitary can be implemented by a 2O(n)2^{O(n)}2O(n)-depth quantum circuit using single- and two-qubit gates. It has been open whether exponential depth is *necessary* for general unitaries, even when allowing an unlimited number of ancilla qubits. Here we show, perhaps surprisingly, that all unitaries can be implemented exactly by a circuit of one- and two-qubit gates of depth poly(n)\mathsf{poly}(n)poly(n) with 2O(n)2^{O(n)}2O(n) ancilla qubits. In other words, every nnn-qubit unitary can be parallelized to polynomial depth. In fact, our depth bound is *linear* in nnn, which is the best possible, and an exponential improvement on the previous best bound of 2n/22^{n/2}2n/2 due to Rosenthal [TQC 2022, Quantum 2026]. Moreover, if we allow unbounded fan-out gates, these circuits can be further reduced to *constant* depth. Our construction takes advantage of a novel relationship connecting the unitary synthesis problem of Aaronson and Kuperberg to locally-decodable codes and private information retrieval from complexity theory and cryptography, and has a natural interpretation in bosonic quantum computation.