Physical Interactions for Fast Quantum Computation - Stephen Fenner

Keeping a quantum superposition coherent during a quantum computation is one of the biggest challenges to quantum computing. If quantum computation is to be of any use, computation time must decrease relative to decoherence time. We consider the power and limits of \\\"ultrafast\\\" quantum computation, modeled by small-depth quantum circuits. To compute anything useful, these circuits must take advantage of multiqubit gates. A particularly useful multiqubit gate is the fan-out gate, which copies the classical value of a single qubit to n-1 other qubits. With fan-out, constant-depth circuits can approximate the Quantum Fourier Transform and modular arithmetic, and hence can carry out the quantum part of Shor\\\'s factoring and discrete log algorithms. I will show that fan-out arises naturally from spin-exchange (Heisenberg) interactions. Thus in principle, one can implement these gates directly, at a cost potentally much lower than expected.