Traditional computers are like microscopic cities. The roads of these cities are wires with electricity coursing through them. These roads have lots of gates, known as logic gates, which enable computers to do their job. Like physical gates that allow or block cars, logic gates allow or block electricity. Electricity that goes through the gates represents a “1” of digital data, and blocked electricity is a “0.”
Logic gates are building blocks for processing information. One kind of logic gate, known as the AND gate, could, for example, quickly determine whether two people agree to a business deal. It takes in two bits of information, and generates a 1 if both incoming bits are 1s. So, if both business people say “yes” (1) to the deal, the AND gate will output 1. If one or both say “no” (0), the AND gate generates a 0 or a no.
By arranging gates in a circuit, engineers can create something akin to a flowchart that enables computers to carry out many kinds of logical operations, such as mathematical calculations—and perform the kinds of tasks that computers can do.
In their quantum logic gate, Monroe, Wineland and colleagues controlled the energy levels in an individual ion so that a lower-energy state represented a 0 and a higher-energy state represented a 1. The ion’s internal energy was the first qubit. They created a second quantum bit with the atom’s external motion: 0 represented less motion and 1 represented a greater amount of motion.
The group entangled the ion’s internal energy state with its overall motion. In the process, they made a quantum version of a CONTROLLED NOT gate. In their gate, the ion’s energy of motion serves the “control” bit. If it is a 1, then it causes the ion’s internal energy state to flip.
Using lasers, the researchers could also cause the ion’s internal energy state to go into a superposition of 0 and 1, putting the ion’s motion into a superposition of 0 and 1. This allows the gate to process multiple possibilities simultaneously, unlike ordinary logic gates, so the gate can consider both the “yes” and “no” possibilities of the business deal at the same time.
This quantum logic gate represented a basic building block of a quantum computer.
What most excited researchers, however, was what would happen when you scaled up this system—with its two qubits—to more qubits.
Multiple qubits entangled with one another could be used to carry out massive numbers of calculations at the same time. Two-qubit gates can process four possible combinations of 0s and 1s simultaneously, and three-qubit gates can process eight possible combinations. Each additional qubit doubles the number of combinations the gate can process at the same time, so there is an exponential increase with each new qubit.
But the power of quantum computation doesn’t come from this feature alone.
“It is often said that the power of quantum computation comes from the ability of quantum computers to perform many computations at the same time in superposition,” says Stephen Jordan, a Microsoft quantum computing researcher who was a longtime NIST staff member and QuICS fellow. “This is sort of true. However, this is not the whole story. For example, to search for a solution to a problem, one might imagine putting a quantum computer into a superposition over all possible solutions. But quantum mechanics does not give us control over how the superposition will collapse,” he says.
“What actually happens is that different computations can indeed be done in superposition, achieving a kind of parallel computing, but the measurement at the end of the computation can only extract a small amount of information about the results of all of these computations. The key is to design the measurement so that it extracts useful global information about the whole set of results from the computations done in superposition, such as detecting periodicities or other patterns,” he explains.
“It is kind of like having a big database, but you can only extract a limited amount of information from it, such as, ‘what is the sum of all the balances in all the bank accounts?’ or ‘How many bank accounts are empty?’ but you can't download the whole thing,” Jordan says.
To understand this, it’s helpful to describe yet another quantum phenomenon known as wave-particle duality.
As physicist Louis de Broglie showed in the 1920s, all objects can either act as particles or waves. An ion can act like a solid ball or it can behave like a rippling wave. As a wave, an ion has peaks and valleys in space; the peaks represent where the ion is more likely to be found when measured. The peaks and valleys of an ion with a qubit value of 0 look different from those for an ion in the 1 state. In a superposition of 0 and 1, the two sets of peaks and valleys add together to create a new wave pattern. Researchers can bring two ions together and line up one ion’s wave with another ion’s wave. The waves will combine or “interfere” to form a new wave pattern. By interfering waves in certain ways, the scientists create patterns that can be converted back into qubit values and yield useful information.
“So, a quantum computation entails creating an even superposition of all possible answers, and then manipulating that superposition,” Boisvert says. “Then, when one makes a measurement, one gets the right answer with high probability.”
“In Shor’s algorithm, the most important step is teasing out a particular property, a repeating wave pattern of sorts, which would be very difficult to determine by brute force, which subsequently can be used to determine the factors,” Boisvert says.