Principles of Superconducting Quantum Computers

11 Quantum Logic: Efficient Implementation of Classical Computations

In this chapter, we describe how to implement classical computations, such as addition and multiplication, using quantum gates. Of course, if your quantum program contains only classical operations on classical data, you’re doing it wrong! We already have fast and inexpensive classical logic gates to do this, and a quantum program should exploit uniquely quantum features, such as phase, superposition, and entanglement.

However, there are very good reasons to consider efficient quantum implementations of classical logic. First, these operations are embedded as kernels in important quantum algorithms, such as Shor’s algorithm for factoring large integers, and Grover’s search algorithm. Second, classical computations can be performed on quantum information, and we will see how logical operations operate on general quantum states. If we had to transfer information from the quantum realm to the classical realm in order to perform arithmetic, we would lose the opportunity to utilize quantum parallelism.

As a motivating example, consider the quantum circuit in Figure 11.1. The function U_ADD is a three-bit adder: it takes the 3-qubit quantum state |x⟩ and the 3-qubit quantum state |y⟩ and produces |(x + y) mod 8⟩, where x and y are interpreted as unsigned binary numbers. Actually, the output of the circuit is |x, x + y⟩, because an output of |x + y⟩ by itself would not be reversible: given only x + y, there’s no way ...