2018/11/14 by Alexandru Paler, Paler, Alexandru, Austin Fowler +4
Computer Science · Engineering · Physics and Astronomy · #Data Structures and Algorithms (cs.DS) #Emerging Technologies (cs.ET) #FOS: Computer and information sciences #FOS: Physical sciences #Low-power high-performance VLSI design #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #cs.DS #cs.ET #quant-ph
paper · pdf · doi:10.48550/arxiv.1811.06011
arxiv created 2018/11/14 · openalex publication_date 2018/11/14 · arxiv updated 2018/11/16 · openalex created_date 2022/08/02 · openalex updated_date 2026/07/28
Large scale quantum computing is highly anticipated, and quantum circuit design automation needs to keep up with the transition from small scale to large scale problems. Methods to support fast quantum circuit manipulations (e.g.~gate replacement, wire reordering, etc.) or specific circuit analysis operations have not been considered important and have been often implemented in a naive manner thus far. For example, quantum circuits are usually represented in term of one-dimensional gate lists or as directed acyclic graphs. Although implementations for quantum circuit manipulations are often only of polynomial complexity, the sheer number of possibilities to consider with increasing scales of quantum computations make these representations highly inefficient -- constituting a serious bottleneck. At the same time, quantum circuits have structural characteristics, which allow for more specific and faster approaches. This work utilises these characteristics by introducing a dedicated representation for large quantum circuits, namely wire label reference diagrams. We apply the representation to a set of very common circuit transformations, and develop corresponding solutions which achieve orders of magnitude performance improvements for circuits which include up to 80 000 qubits and 200 000 gates. The implementation of the proposed method is available online.