A reduction from weak agnostic learning of class C to efficient tomography of states with bounded l1-extent w.r.t. C, with a concrete algorithm for stabilizer states running in poly(n, (ξ/ε)^log(ξ/ε)) time.
Efficient synthesis of linear reversible circuits
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
abstract
In this paper we consider circuit synthesis for n-wire linear reversible circuits using the C-NOT gate library. These circuits are an important class of reversible circuits with applications to quantum computation. Previous algorithms, based on Gaussian elimination and LU-decomposition, yield circuits with O(n^2) gates in the worst-case. However, an information theoretic bound suggests that it may be possible to reduce this to as few as O(n^2/log n) gates. We present an algorithm that is optimal up to a multiplicative constant, as well as Theta(log n) times faster than previous methods. While our results are primarily asymptotic, simulation results show that even for relatively small n our algorithm is faster and yields more efficient circuits than the standard method. Generically our algorithm can be interpreted as a matrix decomposition algorithm, yielding an asymptotically efficient decomposition of a binary matrix into a product of elementary matrices.
fields
quant-ph 3years
2026 3representative citing papers
Restricting phase-polynomial synthesis to allowed CNOTs on a given architecture reduces routing overhead from O(log n) or worse to a constant factor of at most 4.
Pauli and Clifford groups are formulated in complex Geometric Algebra, with Clifford operators generated by π/4-Pauli rotors and a greedy rotor algorithm yielding compact decompositions.
citing papers explorer
-
Tomography of quantum states with bounded extent
A reduction from weak agnostic learning of class C to efficient tomography of states with bounded l1-extent w.r.t. C, with a concrete algorithm for stabilizer states running in poly(n, (ξ/ε)^log(ξ/ε)) time.
-
Qubit Routing for (Almost) Free
Restricting phase-polynomial synthesis to allowed CNOTs on a given architecture reduces routing overhead from O(log n) or worse to a constant factor of at most 4.
-
Geometric Algebra Quantum Gate Decomposition
Pauli and Clifford groups are formulated in complex Geometric Algebra, with Clifford operators generated by π/4-Pauli rotors and a greedy rotor algorithm yielding compact decompositions.