Overview talk (ASPDAC'25 keynote): slides (UCLA Box)
Related Publications
Quantum Layout Synthesis (15 papers)
- Book chapter in Design Automation of Quantum Computers - Layout Synthesis for Near-Term Quantum Computing: Gap Analysis and Optimal Solution
- ICCAD'25 - Routing-Aware Placement for Zoned Neutral Atom-Based Quantum Computing
- QCE'25 - Compilation of QCrank Encoding Algorithm for a Dynamically Programmable Qubit Array Processor
- DAC'25 - Assessing Quantum Layout Synthesis Tools via Known Optimal-SWAP Cost Benchmarks
- HPCA'25 - Reuse-Aware Compilation for Zoned Quantum Architectures Based on Neutral Atoms
- ISPD'25 - ML-QLS: Multilevel Quantum Layout Synthesis
- ASPDAC'25 - Compilation for Dynamically Field-Programmable Qubit Arrays with Efficient and Provably Near-Optimal Scheduling
- Quantum (2024) - Compiling Quantum Circuits for Dynamically Field-Programmable Neutral Atoms Array Processors
- DATE'24 (spotlight on the UCLA CQSE website) - Depth-Optimal Addressing of 2D Qubit Array with 1D Controls Based on Exact Binary Matrix Factorization
- DAC'23 - Scalable Optimal Layout Synthesis for NISQ Quantum Processors
- DAC'23 - Lightning Talk: Scaling Up Quantum Compilation - Challenges and Opportunities
- ICCAD'22 - Qubit Mapping for Reconfigurable Atom Arrays
- ICCAD'21 - Optimal Qubit Mapping with Simultaneous Gate Absorption
- IEEE Transactions on Computers (2021) - Optimality Study of Existing Quantum Computing Layout Synthesis Tools
- ICCAD'20 - Optimal Layout Synthesis for Quantum Computing
Quantum Circuit Synthesis (2 papers)
- ICCAD'24 - Quantum State Preparation Circuit Optimization Exploiting Don't Cares
- DATE'24 - Quantum State Preparation Using an Exact CNOT Synthesis Formulation
Architecture Optimization (1 paper)
- IEEE Journal on Emerging and Selected Topics in Circuits and Systems (2022) - Domain-Specific Quantum Architecture Optimization
Software Release
Benchmarks (2)
- QUEKO: Quantum Mapping Examples with Known Optimal
- QUBIKOS: Quantum Benchmark with Known Optimal SWAP Counts
Compilers (8)
- OLSQ: Optimal Layout Synthesis for Quantum Computing
- OLSQ2: Scalable Optimal Layout Synthesis for NISQ Quantum Processors
- OLSQ-DPQA: Optimal Layout Synthesizer of Quantum Circuits for Dynamically Field-Programmable Qubit Arrays
- EBMF: Exact Binary Matrix Factorization
- Enola: Compilation for Dynamically Field-Programmable Qubit Arrays with Efficient and Provably Near-Optimal Scheduling
- ML-QLS: Multilevel Quantum Layout Synthesis
- ML-Sabre: Multilevel Sabre
- ZAC: Reuse-Aware Compilation for Zoned Quantum Architectures Based on Neutral Atoms
Our lab focuses on advancing quantum compilation techniques to enhance the efficiency and scalability of quantum computing. We focus on Quantum Layout Synthesis (QLS), developing optimal and heuristic methods for mapping quantum algorithms onto hardware, including reconfigurable architectures. Through benchmarking and optimality studies, we evaluate how close current techniques are to the theoretical limits. With the QLS tool, we perform architecture optimization to customize quantum hardware for improving quantum circuit performance. Lastly, we also explore Quantum Circuit Synthesis (QCS), with a focus on logic synthesis for efficient state preparation.
Contents
Compilation in Quantum Computing (QC)
Quantum computing (QC) has been shown, in theory, to hold huge advantages over classical computing. However, there remain many engineering challenges in the implementation of real-world QC applications. In order to divide-and-conquer, we split the task into multiple compilation stages.
The topics that we are particularly interested in are those concerning QC architecture and compilation, which connects algorithms and devices. One of them is layout synthesis for quantum computing (QLS), also named qubit mapping or allocation. A quantum program usually assumes all-to-all connectivity of the qubits, but this is not the case for some QC technologies. QLS aims to transform the programs so that they are executable on actual quantum hardware and, at the same time, overcome some limitations of these near-term devices, e.g. volatile qubits and error-prone quantum gates.
Quantum Layout Synthesis - QLS
The tools we have developed so far are for physical quantum circuits. If the results of these circuits are interpreted directly, the formalism of quantum computing is what we call noisy intermediate-scale quantum computing (NISQ). In the long run, we may construct logical quantum circuits based on quantum error correcting codes, which will translate to a huge amount of physical circuits. This formalism is called fault-tolerant quantum computing (FTQC). Introducing the middle layer of abstraction for error correction changes the compilation fundamentally. FTQC compilation is a future direction of ours, while we focus on physical circuits on this page. Our compilers are general purpose. We have used the following benchmark sets so far. We published QUEKO, a set of QLS benchmarks with known optimal depths and gate counts on given architectures, which can be used to evaluate existing QLS tools and direct future development of such tools. Previously, QLS benchmarks did not provide optimal solutions, so researchers could only compare with each other, but how far are they from the theoretical optimum? This is an NP-hard problem to answer in general but, specifically, the optimal solutions for QUEKO benchmarks on the given architectures are known, so we can measure the optimality gaps with QUEKO. In our study, large gaps were found, even up to 45x on some near-term feasible QUEKO circuits. In addition to circuit depth, the number of two-qubit gates is the other important metric to evaluate compiler performance. To this end, we propose QUBIKOS, a benchmark set with known-optimal SWAP count. We perform evaluation on the grid architecture (Sycamore) and the heavy-hexagon architecture (Eagle). Our study shows that the performance of heuristic tools degrades with sparse connectivity - up to a 400x optimality gap even with the SOTA compiler. With grid connectivity, the SOTA compiler still delivers around a 2x optimality gap, urging the need for high-quality compilation tools. After we revealed the optimality gaps, we went on to develop an optimal/exact QLS tool, OLSQ. We represented the solution space in a more compact way, resulting in orders-of-magnitude reductions in time and memory. By eliminating some redundant variables between mapping transformations, we arrived at a more scalable, nearly-optimal solution, transition-based (TB-) OLSQ. It can reduce SWAP cost by 70% in geomean and increase fidelity by 1.3x in geomean compared to leading related works. We also applied some domain-specific knowledge to adjust TB-OLSQ for the QLS of QAOA circuits, resulting in further reductions in depth and SWAP cost. A microgrant for open-source OLSQ has been granted by Unitary Fund. By analyzing the properties of NISQ applications, we developed three techniques improving qubit mapping quality and efficiency: SWAP absorption, commutation, and alternating matchings, which leads to OLSQ-GA, a qubit mapper that formulates the generalized NISQ mapping problem (with SWAP absorption) using SMT optimization and solves it optimally. Compared to the state-of-the-art optimal method (TB-OLSQ), we reduce depth by up to 50.0% and SWAP count by 100%. We improve fidelity by 9.45% for a single iteration, and 55.9% for 5 iterations on a set of QAOA instances. Compared to heuristic methods, the gaps are even larger. With the rapid development of quantum hardware with 100+ qubits, optimal tools are not able to return a solution in a day due to the exponential runtime growth. Therefore, we propose a hybrid approach, multilevel quantum layout synthesis (ML-QLS), to construct a problem hierarchy by clustering. At the coarsest level, the problem size is small enough to be handled by exact solvers. This solution serves as global optimization information to guide the solving process at the finer levels through a heuristic tool. As the multilevel framework is flexible in terms of the number of levels, we are able to control the tradeoff between runtime and solution quality. To demonstrate that the multilevel framework can be integrated with any heuristic tool to enhance its performance, we use Sabre, the state-of-the-art heuristic tool, in a multilevel scheme. Our work MultilevelSabre shows that with the aid of the multilevel framework, we are able to reduce SWAP count by 60% and depth by 17%, while delivering a 60% compilation time reduction. Because of the large number of qubits available and the massively parallel execution of entangling two-qubit gates, atom arrays are a promising platform for quantum computing. The qubits are selectively loaded into arrays of optical traps, some of which can be moved during the computation itself. By adjusting the locations of the traps and shining a specific global laser, different pairs of qubits, even those initially far away, can be entangled at different stages of the quantum program execution. In comparison, previous QC architectures only generate entanglement on a fixed set of quantum register pairs. Thus, reconfigurable atom arrays (RAA) present a new challenge for QC compilation, especially QLS, which decides the qubit placement and gate scheduling. In our ICCAD'22 paper, we start by systematically examining the fundamental constraints on RAA imposed by physics. Built upon this understanding, we discretize the state space of the architecture, and we formulate layout synthesis for such an architecture as a satisfiability modulo theories (SMT) problem. Finally, we demonstrate our work by compiling the quantum approximate optimization algorithm (QAOA), one of the promising near-term quantum computing applications. Our layout synthesizer reduces the number of required native two-qubit gates in 22-qubit QAOA by 5.72x (geomean) compared to leading experiments on a superconducting architecture. Combined with a better coherence time, there is an order-of-magnitude increase in circuit fidelity. To further scale up our compiler, we learn from our previous experience in VLSI, an approach named iterative peeling. Specifically, we relax our SMT formulation so that each invocation of the solver handles as many gates as possible for one two-qubit gate stage, and the solver is called iteratively until all gates are compiled. As a result, our tool, OLSQ-DPQA, manages to compile larger circuits, e.g., the 90-qubit QAOA MaxCut shown below. This link provides a high-resolution version of the video. In RAA architectures, we apply a global Rydberg laser to enable two-qubit gates. However, every qubit excited by the Rydberg laser accumulates error even if it does not interact with other qubits to perform a gate. Thus, minimizing the number of Rydberg stages is critical to the circuit fidelity. In our ASPDAC'25 paper, we propose Enola with a scheduling algorithm that can achieve a near-optimal Rydberg stage count, and therefore achieves 5.9x fidelity improvement compared to OLSQ-DPQA. Besides the monolithic-zone architectures discussed above, zoned architectures have been proposed to mitigate idle qubit excitation errors by having separate zones for qubit storage and computation. Qubits not involved in gate operations can be stored compactly in the storage zone, shielded from the effect of the Rydberg laser. With this architecture, we would like to optimize the qubit movement between zones, as those movements prolong the circuit execution time and thus cause qubit decoherence errors. In our HPCA'25 paper, we proposed ZAC for the zoned architecture, which significantly reduces qubit movement through the concept of qubit reuse. In addition, our qubit placement strategy effectively minimizes the qubit movement distance. Overall, we demonstrate 22x fidelity improvement over the monolithic architecture. Moreover, ZAC is shown to have only a 10% fidelity gap on average compared to the ideal solution. In addition, ZAC can support advanced architectures with multiple zones or AOD arrays. The animation below shows the Ising model with 98 qubits compiled for an architecture with two entanglement zones and one storage zone. This ability enables ZAC to perform architecture evaluation, facilitating the development of quantum hardware.
Benchmarks - what quantum algorithm we compile?
Optimality study - how far are we from optimal?
Optimal quantum layout synthesis
Multilevel quantum layout synthesis
Layout synthesis for reconfigurable QC architectures
To fully leverage the product incentive of neutral atom architectures, we developed a prototype for optimal arbitrary 1D atom rearrangement with maximum hardware parallelism. It aims to compose and scale up to address complex 2D patterns, enabling QEC code compilation, fault-tolerant architecture design, surgery operations, etc. Current progress: (1) A SAT-based solver and an MILP-based post-process for 1D rearrangement, achieving near-optimal placement and routing in terms of rearrangement depth. (2) An optional feedback loop to further improve duration within the same rearrangement depth by refining the movement sequence using local or global search methods. (3) Preliminary experiments on the Tanner 3-4 classical code enable compilation for the 2D HGP code (up to 900 data qubits), with results showing durations of single-digit milliseconds. Next steps: further demonstrate the advantages of our 1D formulation in (1) fault-tolerant memory; (2) fault-tolerant logical operations; (3) relevant applications such as lattice surgery. Quantum state preparation initializes the quantum registers and is essential for running quantum algorithms. In our DATE'24 paper, we formulate the state preparation problem as a shortest path problem and employ the A* algorithm to find the circuit with the optimal number of CNOTs. Our method represents a milestone as the first design automation algorithm to surpass manual design, reducing the best CNOT count to prepare a Dicke state by 2x. For general states with up to 20 qubits, our method reduces the CNOT count by 9% and 32% for dense and sparse states, respectively, on average, compared to the latest algorithms. In our ICCAD'24 paper, we identify numerous conditions within the quantum circuit where breaking local unitary equivalences does not alter the overall outcome of the state preparation (i.e., don't cares). We introduce a peephole optimization algorithm that identifies such unitaries for replacement in the original circuit. Exploiting these don't-care conditions, our algorithm achieves a 36% reduction in the number of two-qubit gates compared to prior methods that strictly preserve unitary equivalence. In fault-tolerant quantum computing, T gates are supplied via magic state distillation and dominate the space-time cost of a circuit, while Clifford gates incur negligible overhead. Conventional synthesis flows minimize AND count in an {XOR, AND, NOT} basis as a proxy for the T count; however, this approach neglects phase cancellation opportunities and can produce results far from T-optimal. In our DAC'26 paper, we formulate an exact T synthesis problem and canonicalize Boolean functions under Clifford equivalence. By precomputing T-optimal implementations for functions up to seven variables and developing a customized mapper, we reduce the T count by up to 17% on EPFL benchmarks and improve the best-known T counts of several cryptographic modules by up to 40%. Current quantum processors are designed manually and are not targeted at a specific quantum application. In classical computing, customized architectures have demonstrated significant performance and energy efficiency gains over general-purpose counterparts. For quantum computing, the qubit connectivity of quantum processors is an important factor that affects the circuit fidelity, as additional computation overhead is introduced in the QLS stage. Therefore, we focused on customizing qubit connectivity to improve fidelity for a given quantum circuit. We proposed a framework that integrates the optimal QLS tool into the architecture optimization procedure so that the QLS tool searches for the architecture leading to the optimal compilation results. We demonstrate up to 59% fidelity improvement in simulation by optimizing the heavy-hexagon architecture for QAOA MaxCut circuits, and up to 14% improvement on the grid architecture. For the QCNN circuit, architecture optimization improves fidelity by 11% on the heavy-hexagon architecture and 605% on the grid architecture. The unitary cluster Jastrow (UCJ) ansatz and its local variant (LUCJ) are physically motivated and hardware-efficient approaches for variational quantum algorithms in quantum chemistry. Their parameters can be initialized from classical coupled cluster singles and doubles (CCSD) calculations. However, practical constraints, such as limiting the number of ansatz repetitions and adapting interactions to hardware connectivity, degrade the approximation to CCSD and reduce energy accuracy on near-term devices. Therefore, in this project, we develop two architecture-aware parameter initialization techniques to mitigate these effects. First, we apply compressed double factorization of CCSD amplitudes to better preserve the CCSD approximation under circuit depth and connectivity constraints. This method supports both expectation value-based and sample-based quantum algorithms. Second, for sample-based workflows, we incorporate approximate tensor network simulation to improve the fidelity of measurement samples generated by the ansatz circuit. We evaluate our methods using exact state-vector simulations up to 52 qubits and experiments on superconducting quantum processors with up to 65 qubits. Our results demonstrate that architecture-conscious compilation and initialization strategies can substantially improve the performance and robustness of quantum chemistry algorithms under realistic hardware constraints.
Layout prototype for quantum error correction
Quantum Circuit Synthesis - QCS
State preparation circuits optimization
Fault-tolerant arithmetic circuits optimization
Architecture Optimization
Exploring architecture design with layout synthesis
Application and Algorithm
Improve parameter initialization for the (local) unitary cluster Jastrow ansatz