REVIEW 5 cited by
Efficient Synthesis of Linear Reversible Circuits
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
read the original 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.
Forward citations
Cited by 5 Pith papers
-
Learning Clifford-structured quantum unitaries and Hamiltonians
A quasipolynomial-time algorithm finds the closest Clifford unitary to an unknown unitary, enabling tomography of unitaries and Hamiltonians with bounded Clifford decomposition size.
-
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.
-
Algorithmic Polynomial Freiman-Ruzsa Theorems
Small-doubling subsets of F_2^n can now be covered by an explicit, efficiently learned subspace in polynomial time, with matching query lower bounds for classical and quantum algorithms.
-
Geometric Algebra Quantum Gate Decomposition
Reformulates Pauli and Clifford groups in geometric algebra with a greedy rotor decomposition algorithm for Clifford operators and geometric view of Clifford+T universality.
-
Design Automation in Quantum Error Correction
A comprehensive review of automated tools and methods for designing quantum error-corrected circuits, with case studies on T-gate optimization, surface-code layout, ML decoders, and verification.
Discussion (0). Continue with ORCID to comment.