Scalable algorithm simplification using quantum AND logic

Ji Chu, Xiaoyu He, Yuxuan Zhou, Jiahao Yuan, Libo Zhang, Qihao Guo, Yong-Ju Hai, Zhikun Han, Chang-Kang Hu, Wenhui Huang, Hao Jia, Dawei Jiao, Sai Li, Yang Liu, Zhongchu Ni, Lifu Nie, Xianchuang Pan, Jiawei Qiu, Weiwei Wei, Wuerkaixi Nuerbolati, Zusheng Yang, Jiajian Zhang, Zhida Zhang, Wanjing Zou, Yuanzhen Chen, Xiaowei Deng, Xiu–Hao Deng, Ling Hu, Jian Li, Song Liu, Yao Lu, Jingjing Niu, Dian Tan, Yuan Xu, Tongxing Yan, Youpeng Zhong, Fei Yan, Xiaoming Sun, Dapeng YuNature Physics 2022 · DOI

Abstract

Implementing quantum algorithms on realistic devices requires translating high-level global operations into sequences of hardware-native logic gates, a process known as quantum compiling. Physical limitations, such as constraints in connectivity and gate alphabets, often result in unacceptable implementation costs. To enable successful near-term applications, it is crucial to optimize compilation by exploiting the capabilities of existing hardware. Here we implement a resource-efficient construction for a quantum version of AND logic that can reduce the compilation overhead, enabling the execution of key quantum circuits. On a high-scalability superconducting quantum processor, we demonstrate low-depth synthesis of high-fidelity generalized Toffoli gates with up to 8 qubits and Grover’s search algorithm in a search space of up to 64 entries. Our experimental demonstration illustrates a scalable and widely applicable approach to implementing quantum algorithms, bringing more meaningful quantum applications on noisy devices within reach.

Introduction

In the current Noisy Intermediate-Scale Quantum (NISQ) era, the utility of quantum computers is severely constrained by short coherence times and high gate error rates. High-level algorithmic operations must be decomposed into hardware-native gates, such as CNOTs. A major bottleneck is the implementation of multi-qubit controlled gates, like the Toffoli gate. Standard decomposition of an $n$-qubit controlled gate typically requires $O(n^2)$ operations, resulting in a "circuit depth" that often exceeds the device's coherence limits. This research introduces a "QuAND" (Quantum AND) gate that leverages higher energy levels of superconducting qubits to perform reversible logic, reducing circuit depth from quadratic to linear scaling.

Methods: The QuAND Gate and Ancilla Levels

The core innovation is the QuAND gate, which utilizes the third energy level ($|2\rangle$) of a transmon qubit as a temporary "ancilla level." Unlike standard qubits restricted to $|0\rangle$ and $|1\rangle$, the QuAND gate uses a coupler-assisted $iSWAP_{11-20}$ operation to map the state $|11\rangle$ to $|20\rangle$. This allows a "parent" qubit to register the AND result of itself and a "child" qubit in the $|2\rangle$ state.

The QuAND gate architecture, including its truth table, physical implementation via iSWAP transitions, and the multi-qubit embedding/recovery strategy.

The compilation strategy involves two main stages:

  1. Embedding: Cascading QuAND gates to compute the collective AND result of multiple control qubits onto a single target.
  2. Recovery: Using reverse QuAND gates to return the qubits to the computational basis after the primary operation (e.g., a phase flip) is performed.

Key Insights: Scaling and Hardware Compatibility

The QuAND approach achieves $O(n)$ depth for an $n$-qubit controlled-Z (CZ) gate on a 1D chain. However, the logic is flexible; if qubits are arranged in a 2D grid or a tree structure, the depth can be further reduced to $O(\sqrt{n})$ or $O(\log n)$, respectively.

Tree-structured cascading of QuAND gates to achieve logarithmic depth scaling in large-scale quantum circuits.

By using the $|2\rangle$ state only for temporary storage, the system avoids the full complexity of qutrit logic while maintaining the efficiency of higher-dimensional Hilbert spaces. Furthermore, the $iSWAP_{11-20}$ transition is a native capability of superconducting circuits with tunable couplers, making the method highly compatible with existing hardware.

Experimental Results

The researchers validated this approach on a superconducting processor with 8 transmon qubits. Key results include:

  • Generalized Toffoli Gates: Successful synthesis of gates up to 8 qubits. Truth-table fidelities were measured at 89.1% for 4 qubits, 53.2% for 6 qubits, and 39.1% for 8 qubits.
  • Grover’s Search Algorithm: The team demonstrated Grover’s search in spaces of 16 ($2^4$) and 64 ($2^6$) entries. For the 64-entry search, they maintained a success probability of 3.9%, significantly outperforming the 1.5% baseline of random search.
  • Efficiency: A 4-qubit Toffoli gate was executed in just 0.4 μs, highlighting the low-depth advantage.

Limitations and Outlook

The primary limitation remains decoherence, specifically the susceptibility of the $|2\rangle$ state to energy relaxation ($T_1$ errors), which accounted for approximately 70% of the error in the 8-qubit demonstration. Future improvements in the coherence of higher energy levels or the implementation of error-suppression techniques will be vital. Beyond superconducting qubits, this QuAND logic is potentially applicable to other platforms like ion traps or silicon quantum dots by utilizing their respective internal degrees of freedom.

Summary updated

Abstract

Abstract Implementing quantum algorithms on realistic devices requires translating high-level global operations into sequences of hardware-native logic gates, a process known as quantum compiling. Physical limitations, such as constraints in connectivity and gate alphabets, often result in unacceptable implementation costs. To enable successful near-term applications, it is crucial to optimize compilation by exploiting the capabilities of existing hardware. Here we implement a resource-efficient construction for a quantum version of AND logic that can reduce the compilation overhead, enabling the execution of key quantum circuits. On a high-scalability superconducting quantum processor, we demonstrate low-depth synthesis of high-fidelity generalized Toffoli gates with up to 8 qubits and Grover’s search algorithm in a search space of up to 64 entries. Our experimental demonstration illustrates a scalable and widely applicable approach to implementing quantum algorithms, bringing more meaningful quantum applications on noisy devices within reach.
BibTeX
@inproceedings{chu2022scalable,
  author = {Ji Chu and Xiaoyu He and Yuxuan Zhou and Jiahao Yuan and Libo Zhang and Qihao Guo and Yong-Ju Hai and Zhikun Han and Chang-Kang Hu and Wenhui Huang and Hao Jia and Dawei Jiao and Sai Li and Yang Liu and Zhongchu Ni and Lifu Nie and Xianchuang Pan and Jiawei Qiu and Weiwei Wei and Wuerkaixi Nuerbolati and Zusheng Yang and Jiajian Zhang and Zhida Zhang and Wanjing Zou and Yuanzhen Chen and Xiaowei Deng and Xiu–Hao Deng and Ling Hu and Jian Li and Song Liu and Yao Lu and Jingjing Niu and Dian Tan and Yuan Xu and Tongxing Yan and Youpeng Zhong and Fei Yan and Xiaoming Sun and Dapeng Yu},
  title = {{Scalable algorithm simplification using quantum AND logic}},
  booktitle = {Nature Physics},
  year = {2022},
  doi = {10.1038/s41567-022-01813-7},
}
Figure