Computation at a distance
read the original abstract
We consider a model of computation motivated by possible limitations on quantum computers. We have a linear array of n wires, and we may perform operations only on pairs of adjacent wires. Our goal is to build a circuits that perform specified operations spanning all n wires. We show that the natural lower bound of n-1 on circuit depth is nearly tight for a variety of problems, and we prove linear upper bounds for additional problems. In particular, using only gates adding a wire (mod 2) into an adjacent wire, we can realize any linear operation in GL_n(2) as a circuit of depth 5n. We show that some linear operations require depth at least 2n+1.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
Asymptotically Optimal Depth Fermionic Permutation on 2D Grid Quantum Architecture without Ancillas
A fermionic permutation protocol on 2D nearest-neighbor grids achieves the optimal O(sqrt(N)) depth with O(N sqrt(N)) gates, no ancillas, and extends to Jordan-Wigner, Bravyi-Kitaev, and Parity encodings via Hilbert-c...
-
Block Encoding of Sparse Matrices via Coherent Permutation
A new framework for block encoding sparse matrices that uses coherent permutations to reorder amplitudes while preserving superposition and combinatorial optimization to meet hardware connectivity limits.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.