IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

A Bridge-Based Compression Algorithm for Topological Quantum Circuits

Wei-Hsiang Tseng, Chen-Hao Hsu, Wan-Hsuan Lin, Yao-Wen Chang

Published Mar 23, 2022• 3 citations

Abstract

Topological quantum error correction (TQEC) is promising for scalable fault-tolerant quantum computation. The required resource of a TQEC circuit can be modeled as its space-time volume of a three-dimensional geometric description. Implementing a quantum algorithm with a reasonable physical qubit number and computation time is challenging for large-scale complex problems. Therefore, it is desirable to minimize the space-time volume for large-scale TQEC circuits. Previous work proposed bridge compression, which can significantly compress a TQEC circuit, but it was performed manually. This article presents the first automated tool that can perform bridge compression on a large-scale TQEC circuit. Our proposed algorithm applies the bridge compression technique to compactify TQEC circuits with modularization. Besides, we offer a time-ordering-aware 2.5-D placement for compacting TQEC circuits and satisfying time-ordered measurement constraints. On the other hand, we suggest friend net-aware routing to effectively reduce the required routing resource under topological deformation. Compared with the state-of-the-art work, experimental results show that our proposed algorithm can averagely reduce space-time volumes by 84%.

DOI: 10.1109/tcad.2022.3161597

Related papers

A Bridge-based Compression Algorithm for Topological Quantum Circuits

Chen-Hao Hsu, Wan-Hsuan Lin, Wei-Hsiang Tseng +1 more

The topological quantum error correction (TQEC) scheme is promising for scalable and reliable quantum computing. A TQEC circuit can be modeled by a three-dimensional diagram, and the implementation resource of a TQEC circuit is abstracted to its space-time volume. Implementing a quantum algorithm with a reasonable physical qubit number and reasonable computation time is challenging for large-scale practical problems. Therefore, minimizing the space-time volume of a TQEC circuit becomes a crucial issue. Previous work shows that bridge compression can greatly compress TQEC circuits, but it was performed only manually. It is desirable to develop automated compression techniques for TQEC circuits to achieve low-overhead, large-scale quantum computations. In this paper, we present the first work that can automatically perform bridge compression on TQEC circuits. Compared with the state-of-the-art method, experimental results show that our proposed algorithm can averagely reduce space-time volumes by 83%.

ACM/IEEE Design Automation Conference (DAC)Nov 8, 20215 citations

A bridge-based algorithm for simultaneous primal and dual defects compression on topologically quantum-error-corrected circuits

Wei-Hsiang Tseng, Yao‐Wen Chang

Topological quantum error correction (TQEC) using the surface code is among the most promising techniques for fault-tolerant quantum circuits. The required resource of a TQEC circuit can be modeled as a space-time volume of a three-dimensional diagram by describing the defect movement along the time axis. For large-scale complex problems, it is crucial to minimize the space-time volume for a quantum algorithm with a reasonable physical qubit number and computation time. Previous work proposed an automated tool to perform bridge compression on a large-scale TQEC circuit. However, the existing automated bridging compression is only for dual defects and not for primal defects. This paper presents an algorithm to perform bridge compression on primal and dual defects simultaneously. In addition, the automatic compression algorithm performs initialization/measurement simplification and flipping to improve the compression. Compared with the state-of-the-art work, experimental results show that our proposed algorithm can averagely reduce space-time volumes by 47%.

ACM/IEEE Design Automation Conference (DAC)Jul 10, 20223 citations

Late Breaking Results: An Efficient Bridge-based Compression Algorithm for Topologically Quantum Error Corrected Circuits

Wei-Hsiang Tseng, Yao‐Wen Chang

Topological quantum error correction (TQEC) is a promising method for fault-tolerant quantum circuits. A TQEC circuit can be visualized as the defect movement along the time axis and modeled as a 3D space-time volume to estimate the required resource. A quantum algorithm must minimize the space-time volume for a feasible physical qubit number and computational time, especially for large-scale designs. Previous work presents quadratic-time simultaneous primal and dual bridge compression for a TQEC circuit, which is infeasible for large-scale problems. This paper presents an efficient divide-and-conquer approach to primal and dual bridge compression, which can support different code distances between qubits. Compared with the previous work, experimental results show that our algorithm is effective and efficient even for large-scale problems.

ACM/IEEE Design Automation Conference (DAC)Jul 9, 20231 citation

A Bridge-based Algorithm for Simultaneous Primal and Dual Defects Compression on Topologically Quantum-error-corrected Circuits

Wei-Hsiang Tseng, Yao‐Wen Chang

Topological quantum error correction (TQEC) using the surface code is among the most promising techniques for fault-tolerant quantum circuits. The required resource of a TQEC circuit can be modeled as a space-time volume of a three-dimensional diagram by describing the defect movement along the time axis. For large-scale complex problems, it is crucial to minimize the space-time volume for a quantum algorithm with a reasonable physical qubit number and computation time. Previous work proposed an automated tool for bridge compression on a large-scale TQEC circuit. However, the existing automated bridge compression is only for dual defects and not for primal defects. This paper presents an algorithm to simultaneously perform bridge compression on primal and dual defects. In addition, the automatic compression algorithm performs initialization/measurement simplification and flipping to improve the compression. Compared with the state-of-the-art work, experimental results show that our proposed algorithm can averagely reduce space-time volumes by 53%.

ACM Transactions on Design Automation of Electronic SystemsSep 14, 20240 citations

Layout Synthesis for Topological Quantum Circuits With 1-D and 2-D Architectures

Yibo Lin, Bei Yu, Meng Li +1 more

Quantum computing has raised great interests for its potential to achieve an asymptotic speedup on specific problems. Current quantum devices suffer from noise which needs robust and scalable error-correcting schemes. Topological quantum error correction (TQEC) is among the most promising error-correcting techniques with exponential suppression of error with linear increase of space-time complexity. In this paper, we present the first work to explore space-time optimization between 1-D and 2-D architectures for TQEC circuits. We prove the NP-hardness of the qubit routing problem in the layout synthesis and propose an efficient algorithm to optimize space-time volumes for both 1-D and 2-D qubit architectures with promising experimental results.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsOct 6, 201712 citations

Quantum circuit optimization by topological compaction in the surface code

Adam Paetznick, Austin G. Fowler

The fragile nature of quantum information limits our ability to construct large quantities of quantum bits suitable for quantum computing. An important goal, therefore, is to minimize the amount of resources required to implement quantum algorithms, many of which are serial in nature and leave large numbers of qubits idle much of the time unless compression techniques are used. Furthermore, quantum error-correcting codes, which are required to reduce the effects of noise, introduce additional resource overhead. We consider a strategy for quantum circuit optimization based on topological deformation in the surface code, one of the best performing and most practical quantum error-correcting codes. Specifically, we examine the problem of minimizing computation time on a two-dimensional qubit lattice of arbitrary, but fixed dimension, and propose two algorithms for doing so.

arXiv:1304.2807Apr 9, 201319 citations