arXiv:1609.00803 · Physical Review A

Wire recycling for quantum circuit optimization

Alexandru Paler, Robert Wille, Simon J. Devitt

Published Oct 24, 2016• 21 citations

Abstract

Quantum information processing is expressed using quantum bits (qubits) and quantum gates which are arranged in terms of quantum circuits. Here, each qubit is associated with a quantum circuit wire which is used to conduct the desired operations. Most of the existing quantum circuits allocate a single quantum circuit wire for each qubit and hence introduce significant overhead. In fact, qubits are usually not needed during the entire computation, only between their initialization and measurement. Before and after that, corresponding wires may be used by other qubits. In this work, we propose a solution which exploits this fact in order to optimize the design of quantum circuits with respect to the required wires. To this end, we introduce a representation of the lifetimes of all qubits which is used to analyze the respective need for wires. Based on this analysis, a method is proposed which ``recycles'' the available wires and, as a result, reduces the size of the resulting circuit. Numerical tests based on established reversible and fault-tolerant quantum circuits confirm that the proposed solution reduces the number of wires by more than 90% compared to unoptimized quantum circuits.

DOI: 10.1103/physreva.94.042337

Related papers

Qubit Recycling Revisited

Hanru Jiang

Reducing the width of quantum circuits is crucial due to limited number of qubits in quantum devices. This paper revisit an optimization strategy known as qubit recycling (alternatively wire-recycling or measurement- and-reset ), which leverages gate commutativity to reuse discarded qubits, thereby reducing circuit width. We introduce qubit dependency graphs (QDGs) as a key abstraction for this optimization. With QDG, we isolate the computationally demanding components, and observe that qubit recycling is essentially a matrix triangularization problem. Based on QDG and this observation, we study qubit recycling with a focus on complexity, algorithmic, and verification aspects. Firstly, we establish qubit recycling’s NP-hardness through reduction from Wilf’s question, another matrix triangularization problem. Secondly, we propose a QDG-guided solver featuring multiple heuristic options for effective qubit recycling. Benchmark tests conducted on RevLib illustrate our solver’s superior or comparable performance to existing alternatives. Notably, it achieves optimal solutions for the majority of circuits. Finally, we develop a certified qubit recycler that integrates verification and validation techniques, with its correctness proof mechanized in Coq.

Proceedings of the ACM on Programming LanguagesJun 20, 20246 citations

A Framework for Quantum Circuit Optimization: Comparators as a Case Study

Francisco José Orts, Rodrigo Gil-Merino

Qubits are the minimum unit of information in quantum computing. As current quantum devices have a very limited number of available qubits, finding circuits that optimize their use is crucial for this computing paradigm. Optimizing the qubits needed to implement a quantum circuit is not trivial, as these circuits have important restrictions such as the impossibility of copying values or the requirement that the computation done in them must always be reversible. This paper presents a framework for optimizing circuits for quantum computing. The framework is able to obtain, given a quantum circuit, an equivalent one that is more efficient in terms of number of qubits. In particular, the framework has applicability in quantum circuits dedicated to arithmetic operations such as addition or multiplication. As a representative case study, it is applied to a reversible comparator circuit, obtaining a design that reduces the number of qubits and controlled gates compared to other reversible comparators reported in the recent literature. As part of the work, a public repository is included with the necessary code to simplify any other circuit.

IEEE Transactions on ComputersDec 12, 20250 citations

Quantum Circuit Optimization of Arithmetic Circuits using ZX Calculus

Aravind K. Joshi, Akshara Kairali, Renju Raju +2 more

Quantum computing is an emerging technology in which quantum mechanical properties are suitably utilized to perform certain compute-intensive operations faster than classical computers. Quantum algorithms are designed as a combination of quantum circuits that each require a large number of quantum gates, which is a challenge considering the limited number of qubit resources available in quantum computing systems. Our work proposes a technique to optimize quantum arithmetic algorithms by reducing the hardware resources and the number of qubits based on ZX calculus. We have utilized ZX calculus rewrite rules for the optimization of fault-tolerant quantum multiplier circuits where we are able to achieve a significant reduction in the number of ancilla bits and T-gates as compared to the originally required numbers to achieve fault-tolerance. Our work is the first step in the series of arithmetic circuit optimization using graphicalrewrite tools and it pavesthe way for advancing the optimization of various complex quantum circuits and establishing the potential for new applications of the same.

International Journal of Innovative Technology and Exploring EngineeringJan 27, 20240 citations

Doubly Optimal Parallel Wire Cutting without Ancilla Qubits

Hiroyuki Harada, Kaito Wada, Naoki Yamamoto

A restriction in the quality and quantity of available qubits presents a substantial obstacle to the application of near-term and early fault-tolerant quantum computers in practical tasks. To confront this challenge, some techniques for effectively augmenting the system size through classical processing have been proposed; one promising approach is quantum circuit cutting. The main idea of quantum circuit cutting is to decompose an original circuit into smaller subcircuits and combine outputs from these subcircuits to recover the original output. Although this approach enables us to simulate larger quantum circuits beyond physically available circuits, it needs classical overheads quantified by two metrics: the sampling overhead in the number of measurements to reconstruct the original output, and the number of channels in the decomposition. Thus, it is crucial to devise a decomposition method that minimizes both of these metrics, thereby reducing the overall execution time. This paper studies the problem of decomposing the n -qubit identity channel, i.e., n -parallel wire cutting, into a set of local operations and classical communication; then we give an optimal wire-cutting method composed of channels based on mutually unbiased bases that achieves minimal overheads in both the sampling overhead and the number of channels, without ancilla qubits. This is in stark contrast to the existing method that achieves the optimal sampling overhead yet with ancilla qubits. Moreover, we derive a tight lower bound on the number of channels in parallel wire cutting without ancilla systems and show that only our method achieves this lower bound among the existing methods. Notably, our method shows an exponential improvement in the number of channels, compared to the aforementioned ancilla-assisted method that achieves optimal sampling overhead. Our work significantly alleviates the additional overheads for the wire-cutting method and may provide essential components for the early success of quantum computing. Published by the American Physical Society 2024

arXiv:2303.07340PRX QuantumOct 18, 202422 citations

Quantum Circuit Optimization of Arithmetic circuits using ZX Calculus

Aravind K. Joshi, Akshara Kairali, Raju, Renju +4 more

Quantum computing is an emerging technology in which quantum mechanical properties are suitably utilized to perform certain compute-intensive operations faster than classical computers. Quantum algorithms are designed as a combination of quantum circuits that each require a large number of quantum gates, which is a challenge considering the limited number of qubit resources available in quantum computing systems. Our work proposes a technique to optimize quantum arithmetic algorithms by reducing the hardware resources and the number of qubits based on ZX calculus. We have utilised ZX calculus rewrite rules for the optimization of fault-tolerant quantum multiplier circuits where we are able to achieve a significant reduction in the number of ancilla bits and T-gates as compared to the originally required numbers to achieve fault-tolerance. Our work is the first step in the series of arithmetic circuit optimization using graphical rewrite tools and it paves the way for advancing the optimization of various complex quantum circuits and establishing the potential for new applications of the same.

arXiv:2306.02264Jun 4, 20231 citation

Scalable Circuit Cutting: A Framework for Combined Gate and Wire Cuts Using Gate Groups

Fiona Jiali Fröhler, Yannick Stade, Christian Ufrecht +2 more

Quantum circuit cutting enables the execution of large circuits on devices with a limited number of qubits by partitioning circuits into independent subcircuits. However, this introduces a sampling overhead, which grows exponentially with the number of cuts, rendering the choice of cut placements critical for practical circuit cutting. Determining optimal cut placements remains computationally challenging, particularly as circuits grow in size. Additionally, existing circuit cutting approaches typically treat gate and wire cuts independently. Those combining both cutting approaches, however, do not take advantage of joint cutting, i.e., identifying common gate groups and cutting them jointly for a reduced overhead. This work presents a unified framework that combines gate and wire cutting within a single partitioning strategy, enabling more efficient circuit decompositions. Moreover, our approach incorporates joint cutting via a novel gate grouping technique, further reducing sampling overhead. By formulating the cut placement problem as a scalable graph partitioning task, our method efficiently identifies near-optimal cut placements for large circuits, also providing diagnostic feedback on whether circuits are suitable for cutting.

quant-pharXiv:2608.05287Aug 7, 20260 citations