Name
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. |
Year | Venue | Keywords |
|---|---|---|
2007 | Chicago J. Theor. Comput. Sci. | model of computation,linear operator,upper bound,quantum physics,lower bound,quantum computer |
Field | DocType | Volume |
Linear operation,Discrete mathematics,Combinatorics,Upper and lower bounds,Quantum computer,Model of computation,Electronic circuit,Mathematics,Computation | Journal | 2007 |
Citations | PageRank | References |
6 | 0.84 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel A. Kutin | 1 | 65 | 5.63 |
| David Petrie Moulton | 2 | 11 | 3.38 |
| Lawren M. Smithline | 3 | 6 | 0.84 |