Basic Algorithmic Building Blocks and Architecture
We have found that the most important features for efficient algorithm
execution are, in order of importance:
Concurrency. Without concurrent gates, it is impossible for the
circuit depth for an algorithm to be better than its
computational complexity.
Number of qubits. With a large enough number of logical
qubits, it is often possible to parallelize execution of an algorithm.
Interconnection topology. We have shown that a fully-connected quantum
computer (AC) can achieve O(log n) circuit depth for
some circuits that necessarily require O(n) time on
nearest-neighbor-only (NTC) architectures.
Instruction set. For some sets of possible gates, it is
known that emulating some gates requires a polynomial overhead.
