Multibit C k NOT quantum gates via Rydberg blockade

We show that a set of gates that consists of all one-bit quantum gates (U(2)) and the two-bit exclusive-or gate (that maps Boolean values \((x,y)\) to \((x,x \oplus y)\)) is universal in the sense that all unitary operations on arbitrarily many bits \(n\) (U(\(2^n\))) can be expressed as compositions of these gates. We investigate the number of the above gates required to implement other gates, such as generalized Deutsch-Toffoli gates, that apply a specific U(2) transformation to one input bit if and only if the logical AND of all remaining input bits is satisfied. These gates play a central role in many proposed constructions of quantum computational networks. We derive upper and lower bounds on the exact number of elementary gates required to build up a variety of two-and three-bit quantum gates, the asymptotic number required for \(n\)-bit Deutsch-Toffoli gates, and make some observations about the number required for arbitrary \(n\)-bit unitary operations.

In theory, quantum computers can efficiently simulate quantum physics, factor large numbers and estimate integrals, thus solving otherwise intractable computational problems. In practice, quantum computers must operate with noisy devices called ``gates'' that tend to destroy the fragile quantum states needed for computation. The goal of fault-tolerant quantum computing is to compute accurately even when gates have a high probability of error each time they are used. Here we give evidence that accurate quantum computing is possible with error probabilities above 3% per gate, which is significantly higher than what was previously thought possible. However, the resources required for computing at such high error probabilities are excessive. Fortunately, they decrease rapidly with decreasing error probabilities. If we had quantum resources comparable to the considerable resources available in today's digital computers, we could implement non-trivial quantum computations at error probabilities as high as 1% per gate.

Rydberg atoms with principal quantum number n >> 1 have exaggerated atomic properties including dipole-dipole interactions that scale as n^4 and radiative lifetimes that scale as n^3. It was proposed a decade ago to take advantage of these properties to implement quantum gates between neutral atom qubits. The availability of a strong, long-range interaction that can be coherently turned on and off is an enabling resource for a wide range of quantum information tasks stretching far beyond the original gate proposal. Rydberg enabled capabilities include long-range two-qubit gates, collective encoding of multi-qubit registers, implementation of robust light-atom quantum interfaces, and the potential for simulating quantum many body physics. We review the advances of the last decade, covering both theoretical and experimental aspects of Rydberg mediated quantum information processing.