arXiv:2503.00822

Scalable Memory Recycling for Large Quantum Programs

Israel Reichental, Alon, Ravid, Lior Preminger, Matan Vax, Amir Naveh

Published Mar 2, 2025• 0 citations

Abstract

As quantum computing technology advances, the complexity of quantum algorithms increases, necessitating a shift from low-level circuit descriptions to high-level programming paradigms. This paper addresses the challenges of developing a compilation algorithm that optimizes memory management and scales well for bigger, more complex circuits. Our approach models the high-level quantum code as a control flow graph and presents a workflow that searches for a topological sort that maximizes opportunities for qubit reuse. Various heuristics for qubit reuse strategies handle the trade-off between circuit width and depth. We also explore scalability issues in large circuits, suggesting methods to mitigate compilation bottlenecks. By analyzing the structure of the circuit, we are able to identify sub-problems that can be solved separately, without a significant effect on circuit quality, while reducing runtime significantly. This method lays the groundwork for future advancements in quantum programming and compiler optimization by incorporating scalability into quantum memory management.

DOI: 10.48550/arxiv.2503.00822

Related papers

Dynamic Quantum Circuit Compilation

Kun Fang, Munan Zhang, Ruqi Shi +1 more

The practical applications of quantum computing is currently limited by the small number of available qubits. Recent advances in quantum hardware have introduced midcircuit measurements and resets, enabling the reuse of measured qubits and thus reducing the qubit requirements for executing quantum algorithms. In this work, we present a systematic study of dynamic quantum circuit compilation, a process that transforms static quantum circuits into their dynamic equivalents with fewer qubits through qubit reuse. We establish the first graph-based framework for optimizing qubit-reuse compilation. In particular, we characterize the task of finding the optimal compilation strategy for maximizing qubit reuse using binary integer programming and provide efficient heuristic algorithms for devising general compilation strategies. We conduct a thorough analysis of quantum circuits with practical relevance and offer their optimal qubit-reuse compilation strategies. We also perform a comparative analysis against state-of-the-art approaches, demonstrating the superior performance of our methods in both structured and random quantum circuits. Our framework lays a rigorous foundation for understanding dynamic quantum circuit compilation via qubit reuse, holding significant promise for the practical implementation of large-scale quantum algorithms on quantum computers with limited resources.

arXiv:2310.11021IEEE Transactions on ComputersDec 15, 20257 citations

Optimal Qubit Reuse for Quantum Computation with Gate Reordering and Eager Measurement

Wenjian Yu, Tian-Fu Chen, Ying‐Nan Chan +3 more

Qubit capacity is a common bottleneck in quantum computers, limiting the ability to run complex algorithms and slowing the advancements in quantum computing applications. Reusing qubits by resetting them after measuring and repurposing them for subsequent gate operations offers an effective strategy to reduce the overall qubit requirements. Based on Satisfiability Modulo Theories (SMT) and Integer Linear Programming (ILP), we present an optimal algorithm that maximizes qubit reuse while optionally constraining the circuit depth to a specified upper bound. Our approach considers all feasible circuit rearrangements to enhance optimality, including gate reordering and eager measurement. We further propose a divide-and-conquer approach to scale for large circuits by relaxing the optimality guarantee. Experimental results show that our exact method substantially decreases both the qubit count and the circuit depth compared to the current state of the art, while the divide-and-conquer approach effectively addresses scalability issues with maintained solution quality.

IEEE International Conference on Quantum Computing and Engineering (QCE)Aug 30, 20250 citations

Exploiting the Regular Structure of Modern Quantum Architectures for Compiling and Optimizing Programs with Permutable Operators

Yuwei Jin, Fei Hua, Yanhao Chen +3 more

A critical feature in today's quantum circuit is that they have permutable two-qubit operators. The flexibility in ordering the permutable two-qubit gates leads to more compiler optimization opportunities. However, it also imposes significant challenges due to the additional degree of freedom. Our Contributions are two-fold. We first propose a general methodology that can find structured solutions for scalable quantum hardware. It breaks down the complex compilation problem into two sub-problems that can be solved at small scale. Second, we show how such a structured method can be adapted to practical cases that handle sparsity of the input problem graphs and the noise variability in real hardware. Our evaluation evaluates our method on IBM and Google architecture coupling graphs for up to 1,024 qubits and demonstrate better result in both depth and gate count - by up to 72% reduction in depth, and 66% reduction in gate count. Our real experiments on IBM Mumbai show that we can find better expected minimal energy than the state-of-the-art baseline.

International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)Mar 25, 20236 citations

ScaffCC

Ali Javadi-Abhari, Shruti R. Patil, Daniel Kudrow +4 more

Quantum computing is a promising technology for high-performance computation, but requires mature toolflows that can map large-scale quantum programs onto targeted hardware. In this paper, we present a scalable compiler for large-scale quantum applications, and show the opportunities for reducing compilation and analysis time, as well as output code size. We discuss the similarities and differences between compiling for a quantum computer as opposed to a classical computer, and present a state-of-the-art approach for compilation of classical circuits into quantum circuits. Our work also highlights the importance of high-level quantum compilation for logical circuit translation, quantitative analysis of algorithms, and optimization of circuit lengths.

ACM International Conference on Computing Frontiers (CF)May 20, 2014152 citations

Program compilation for large-scale quantum computers

Giulia Meuli

Practical realizations of quantum computers are poised to deliver outstanding computational capabilities far beyond the reach of any classical supercomputer. While classical systems are reliably implemented using CMOS technology, the fabrication of quantum hardware has not yet reached a commercially viable level of maturity. Nowadays, many different technologies are being developed as competing candidates to build the first error-corrected quantum computer. Among the software resources required to operate such a system, quantum compilers translate a high-level description of a quantum algorithm into low-level, technology-dependent quantum instructions. Many quantum algorithms, including Shor's and Grover's algorithms, require to compute some classical logic functions on the quantum computer. The first part of this thesis deals with the problem of compiling quantum circuits that perform such classical Boolean functions, called oracles, into a fault-tolerant set of instructions. Oracle circuits often demand many resources in terms of the number of qubits and gates. The focus is on compiling quantum circuits starting from multi-level logic networks representing large Boolean functions while minimizing the resource footprint of the obtained quantum circuits. At the same time, the trade-off between memory resources and the number of operations typical of such a compilation process is explored. As part of the effort in reducing the resources required to perform a given quantum program, I also present some quantum circuit optimization techniques. The researched algorithms leverage data structures and techniques borrowed and adapted from classical logic synthesis, e.g., SAT solvers, LUT mapping, and multi-level logic networks. I implemented all the compilation algorithms presented in this thesis as part of open-source projects. In particular, I develop and maintain caterpillar---a C++ header-only library dedicated to the quantum compilation of oracles and quantum memory management. The second part of this thesis describes how to equip quantum programming language compilers with automatic accuracy management. Despite the availability of many of such languages, resource estimation of quantum algorithms does not yet support taking approximation errors into account. This general methodology is applicable to any programming language and I demonstrate its integration into the Q# compiler. The technique consists of providing language support to ease the accuracy-aware programming task. The user can define accuracy parameters that will be automatically optimized according to a constraint and a cost function directly generated from the source code. In the presented practical evaluations, the constraint function is the overall allowed accuracy, while the cost function is application-dependent and related to the number of gates. During the optimization process, such functions are evaluated hundreds of times. For this reason, we extract them as (near-)symbolic expressions, whose evaluation time does not depend on the quantum algorithm size. The algorithms and the methodologies presented in this thesis are part of a widespread effort of the research community to build a complete and efficient software stack to program and control the first practical universal quantum computer.

Jan 1, 20201 citation

Quantum Computing Program Compilation and Optimization Theory

Jincheng Zhang

This paper presents a novel theory for quantum computing program compilation and optimization. The core of this theory lies in translating high-level quantum programs into efficient quantum circuit implementations. This is achieved through the utilization of an abstract syntax tree (AST) derived from the quantum program. A compilation algorithm is designed to traverse the AST and generate corresponding quantum circuits, incorporating optimization strategies throughout the process. The work addresses a significant challenge within quantum computing – the complexity of program compilation – and proposes a new theoretical framework to facilitate the development of more practical and performant quantum algorithms. The theoretical framework outlined here provides a foundation for future research and development in quantum compiler design.

Aug 29, 20260 citations