Quantum Researchers Discover the AND Gate

New fundamental operation could reduce overhead for quantum-computing applications

4 min read
Red and blue rectangles surrounded by circuitry

A microscope image of a new quantum AND gate implemented on a superconducting quantum processor. Red and blue indicate lower and higher fixed-frequency superconducting qubits, respectively.

Southern University of Science and Technology/Springer Nature

As powerful as quantum computers may one day prove, quantum physics can make it challenging for the machines to carry out quantum versions of the most basic computing operations. Now scientists in China have created a more practical quantum version of the simple AND operation, which may help quantum computing reach successful near-term applications.

Conventional electronics nowadays rely on transistors, which flick on or off to symbolize data as ones and zeroes. They connect transistors together to build devices known as logic gates, which implement logical operations such as AND, OR, and NOT. Logic gates are the building blocks of all digital circuits.

In contrast, quantum computers depend on components known as quantum bits or “qubits.” These can exist in a quantum state known as superposition, in which they are essentially both 1 and 0 at the same time. Quantum computers work by running quantum algorithms, which describe sequences of elementary operations called quantum logic gates applied to a set of qubits.

“Our work will help narrow the gap between the most anticipated near-term applications and existing noisy devices.”
—Fei Yan, Southern University of Science and Technology, Shenzhen, China

Superposition essentially lets each qubit perform two calculations at once. The more qubits a quantum computer has, the greater its computational power can grow in an exponential fashion. With enough qubits, a quantum computer could theoretically vastly outperform all classical computers on a number of tasks. For instance, on quantum computers, Shor’s algorithm can crack modern cryptography, and Grover’s algorithm is useful for searching databases at sometimes staggering speeds.

However, quantum computers face a physical limitation: All quantum operations must be reversible in order to work. In other words, a quantum computer may perform an operation only if it can also carry out an opposite operation that returns it to its original state. (Reversibility is necessary until a quantum computation is run and its results measured.)

In everyday life, many actions are reversible—for example, you can both tie and untie shoelaces. Others are irreversible—for instance, you can cook an egg but not uncook it.

Similarly, a number of logical operations are reversible—you could apply the NOT operation to a variable and then apply it again to return it to its original state. Others are generally irreversible—you could add 2 and 2 together to get an outcome of 4, a mathematical version of the AND operation, but you could not reverse the operation and know an outcome of 4 began as 2 and 2 unless you knew what at least one of the original variables was.

The AND gate is a fundamental ingredient of both classical and quantum algorithms. However, the demand for reversibility in quantum computing makes it challenging to implement. One workaround is to essentially use an extra or “ancilla qubit for each AND gate that stores the data needed to reverse the operation.

However, quantum computers are currently noisy intermediate-scale quantum (NISQ) platforms, meaning their qubits number up to a few hundred at most and are error-ridden as well. Given quantum computing’s primitive state right now, it would prove “extremely cumbersome to design and build hardware for accommodating extra ancilla qubits on an already crowded processor,” says study cosenior author Fei Yan, a quantum physicist at the Southern University of Science and Technology in Shenzhen, China.

“Our technique presents a scaling advantage. The more qubits are involved, the more cost-saving our technique would be compared to the traditional one.”
—Fei Yan

Now Yan and his colleagues have constructed a new quantum version of the AND gate that removes this need for ancilla qubits. By getting rid of this overhead, they say, their new strategy could make quantum computing more efficient and scalable than ever.

“Our work will help narrow the gap between the most anticipated near-term applications and existing noisy devices,” Yan says. “We hope to see quantum AND functionality added to quantum programs on machines elsewhere, such as the IBM quantum cloud, and played with by more people.”

Instead of using ancilla qubits, the new quantum AND gate relies on the fact that qubits often can encode more than just zeroes and ones. In the new study, the researchers have qubits encode three states. This extra state temporarily holds the data needed to perform the AND operation.

“We do not use any ancilla qubits,” Yan says. “Instead, we use ancilla states.”

In the new study, the scientists implemented quantum AND gates on a superconducting quantum processor with tunable-coupling architecture. Google also employs this architecture with its quantum computers, and IBM plans to start using it in 2023.

“We think that our scheme is well-suited for superconducting qubit systems where ancilla states are abundant and easy to access,” Yan says.

In experiments, the researchers used their quantum AND gate to help construct Toffoli gates, with which quantum computers can implement any classical circuit. Toffoli gates are key elements of many quantum-computing applications, such as Shor’s and Grover’s algorithms and quantum error-correction schemes.

In addition, with six qubits the researchers could run Grover’s algorithm on a database with up to 64 entries. “To our knowledge, previous demonstrations of Grover’s search on any system was limited to 16 entries,” Yan says. This highlights the way in which the quantum AND operation can help scale up quantum computing, he adds.

All in all, “what we really want to emphasize is that our technique presents a scaling advantage,” Yan says. “The more qubits are involved, the more cost-saving our technique would be compared to the traditional one.”

Although these experiments were conducted with superconducting qubits, Yan notes that their quantum AND gate could get implemented with other quantum-computing platforms, “such as trapped ions and semiconductor qubits, by utilizing appropriate ancilla levels.”

The scientists detailed their findings online 14 November in the journal Nature Physics.

The Conversation (0)