publications
2024
- ASPLOSFermihedral: On the Optimal Compilation for Fermion-to-Qubit EncodingYuhao Liu, Shize Che, Junyu Zhou, and 2 more authorsASPLOS, 2024
This paper introduces Fermihedral, a compiler framework focusing on discovering the optimal Fermion-to-qubit encoding for targeted Fermionic Hamiltonians. Fermion-to-qubit encoding is a crucial step in harnessing quantum computing for efficient simulation of Fermionic quantum systems. Utilizing Pauli algebra, Fermihedral redefines complex constraints and objectives of Fermion-to-qubit encoding into a Boolean Satisfiability problem which can then be solved with high-performance solvers. To accommodate larger-scale scenarios, this paper proposed two new strategies that yield approximate optimal solutions mitigating the overhead from the exponentially large number of clauses. Evaluation across diverse Fermionic systems highlights the superiority of Fermihedral, showcasing substantial reductions in implementation costs, gate counts, and circuit depth in the compiled circuits. Real-system experiments on IonQ’s device affirm its effectiveness, notably enhancing simulation accuracy.
@article{fermihedral, author = {Liu, Yuhao and Che, Shize and Zhou, Junyu and Shi, Yunong and Li, Gushu}, title = {Fermihedral: On the Optimal Compilation for Fermion-to-Qubit Encoding}, year = {2024}, isbn = {979-8-4007-0386}, publisher = {Association for Computing Machinery}, address = {La Jolla, CA, USA}, url = {https://doi.org/10.1145/3620666.3651371}, doi = {10.1145/3620666.3651371}, journal = {ASPLOS}, location = {La Jolla, CA, USA}, series = {ASPLOS '24}, } - ASPLOSElivagar: Efficient Quantum Circuit Search for ClassificationSashwat Anagolum, Narges Alavisamani, Poulami Das, and 3 more authorsASPLOS, 2024
@article{elivagar, author = {Anagolum, Sashwat and Alavisamani, Narges and Das, Poulami and Qureshi, Moinuddin and Kessler, Eric and Shi, Yunong}, title = {Elivagar: Efficient Quantum Circuit Search for Classification}, year = {2024}, publisher = {Association for Computing Machinery}, address = {San Diego, CA, USA}, journal = {ASPLOS}, keywords = {quantum machine learning, compilation}, location = {San Diego, CA, USA}, series = {ASPLOS '24}, }
2023
- HPCAA Pulse Generation Framework with Augmented Program-aware Basis Gates and Criticality AnalysisYanhao Chen, Yuwei Jin, Fei Hua, and 4 more authorsHPCA, 2023
@article{hpca23_pulse, author = {Chen, Yanhao and Jin, Yuwei and Hua, Fei and Yayes, Ari and Li, Ang and Shi, Yunong and Zhang, Eddy Z.}, journal = {HPCA}, title = {A Pulse Generation Framework with Augmented Program-aware Basis Gates and Criticality Analysis}, year = {2023} } - HPCAThe Imitation Game: Leveraging CopyCats for Robust Native Gate Selection in NISQ ProgramsPoulami Das, Eric Kessler, and Yunong ShiHPCA, 2023
@article{hpca23_imitation_game, author = {Das, Poulami and Kessler, Eric and Shi, Yunong}, journal = {HPCA}, title = {The Imitation Game: Leveraging CopyCats for Robust Native Gate Selection in NISQ Programs}, year = {2023}, }
2022
- ASPLOSPaulihedral: A Generalized Block-Wise Compiler Optimization Framework for Quantum Simulation KernelsGushu Li, Anbang Wu, Yunong Shi, and 3 more authorsASPLOS, 2022
The quantum simulation kernel is an important subroutine appearing as a very long gate sequence in many quantum programs. In this paper, we propose Paulihedral, a block-wise compiler framework that can deeply optimize this subroutine by exploiting high-level program structure and optimization opportunities. Paulihedral first employs a new Pauli intermediate representation that can maintain the high-level semantics and constraints in quantum simulation kernels. This naturally enables new large-scale optimizations that are hard to implement at the low gate-level. In particular, we propose two technology-independent instruction scheduling passes, and two technology-dependent code optimization passes which reconcile the circuit synthesis, gate cancellation, and qubit mapping stages of the compiler. Experimental results show that Paulihedral can outperform state-of-the-art compiler infrastructures in a wide-range of applications on both near-term superconducting quantum processors and future fault-tolerant quantum computers.
@article{10.1145/3503222.3507715, author = {Li, Gushu and Wu, Anbang and Shi, Yunong and Javadi-Abhari, Ali and Ding, Yufei and Xie, Yuan}, title = {Paulihedral: A Generalized Block-Wise Compiler Optimization Framework for Quantum Simulation Kernels}, year = {2022}, isbn = {9781450392051}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3503222.3507715}, doi = {10.1145/3503222.3507715}, journal = {ASPLOS}, pages = {554–569}, numpages = {16}, keywords = {quantum simulation, compiler, quantum computing}, location = {Lausanne, Switzerland}, series = {ASPLOS '22}, } - HPCADigiQ: A Scalable Digital Controller for Quantum Computers Using SFQ LogicMohammad Reza Jokar, Richard Rines, Ghasem Pasandi, and 5 more authorsHPCA, 2022
@article{9773260, author = {Jokar, Mohammad Reza and Rines, Richard and Pasandi, Ghasem and Cong, Haolin and Holmes, Adam and Shi, Yunong and Pedram, Massoud and Chong, Frederic T.}, journal = {HPCA}, title = {DigiQ: A Scalable Digital Controller for Quantum Computers Using SFQ Logic}, year = {2022}, volume = {}, number = {}, pages = {400-414}, doi = {10.1109/HPCA53966.2022.00037}, } - PLDIGiallar: Push-Button Verification for the Qiskit Quantum CompilerRunzhou Tao, Yunong Shi, Jianan Yao, and 5 more authorsPLDI, 2022
This paper presents Giallar, a fully-automated verification toolkit for quantum compilers. Giallar requires no manual specifications, invariants, or proofs, and can automatically verify that a compiler pass preserves the semantics of quantum circuits. To deal with unbounded loops in quantum compilers, Giallar abstracts three loop templates, whose loop invariants can be automatically inferred. To efficiently check the equivalence of arbitrary input and output circuits that have complicated matrix semantics representation, Giallar introduces a symbolic representation for quantum circuits and a set of rewrite rules for showing the equivalence of symbolic quantum circuits. With Giallar, we implemented and verified 44 (out of 56) compiler passes in 13 versions of the Qiskit compiler, the open-source quantum compiler standard, during which three bugs were detected in and confirmed by Qiskit. Our evaluation shows that most of Qiskit compiler passes can be automatically verified in seconds and verification imposes only a modest overhead to compilation performance.
@article{10.1145/3519939.3523431, author = {Tao, Runzhou and Shi, Yunong and Yao, Jianan and Li, Xupeng and Javadi-Abhari, Ali and Cross, Andrew W. and Chong, Frederic T. and Gu, Ronghui}, title = {Giallar: Push-Button Verification for the Qiskit Quantum Compiler}, year = {2022}, isbn = {9781450392655}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3519939.3523431}, doi = {10.1145/3519939.3523431}, journal = {PLDI}, pages = {641–656}, numpages = {16}, keywords = {compiler verification, automated verification, quantum computing}, location = {San Diego, CA, USA}, series = {PLDI 2022}, }
2021
- PLDIGleipnir: Toward Practical Error Analysis for Quantum ProgramsRunzhou Tao, Yunong Shi, Jianan Yao, and 3 more authorsPLDI 2021, 2021
Practical error analysis is essential for the design, optimization, and evaluation of Noisy Intermediate-Scale Quantum(NISQ) computing. However, bounding errors in quantum programs is a grand challenge, because the effects of quantum errors depend on exponentially large quantum states. In this work, we present Gleipnir, a novel methodology toward practically computing verified error bounds in quantum programs. Gleipnir introduces the (ρ,δ)-diamond norm, an error metric constrained by a quantum predicate consisting of the approximate state ρ and its distance δ to the ideal state ρ. This predicate (ρ,δ) can be computed adaptively using tensor networks based on the Matrix Product States. Gleipnir features a lightweight logic for reasoning about error bounds in noisy quantum programs, based on the (ρ,δ)-diamond norm metric. Our experimental results show that Gleipnir is able to efficiently generate tight error bounds for real-world quantum programs with 10 to 100 qubits, and can be used to evaluate the error mitigation performance of quantum compiler transformations.
@article{10.1145/3453483.3454029, author = {Tao, Runzhou and Shi, Yunong and Yao, Jianan and Hui, John and Chong, Frederic T. and Gu, Ronghui}, title = {Gleipnir: Toward Practical Error Analysis for Quantum Programs}, year = {2021}, isbn = {9781450383912}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3453483.3454029}, doi = {10.1145/3453483.3454029}, journal = {PLDI 2021}, pages = {48–64}, numpages = {17}, keywords = {quantum programming, approximate computing, error analysis}, location = {Virtual, Canada}, series = {PLDI 2021}, } - NANOCOMOn the Co-Design of Quantum Software and HardwareGushu Li, Anbang Wu, Yunong Shi, and 3 more authorsNANOCOM, 2021
A quantum computing system naturally consists of two components, the software system and the hardware system. Quantum applications are programmed using the quantum software and then executed on the quantum hardware. However, the performance of existing quantum computing system is still limited. Solving a practical problem that is beyond the capability of classical computers on a quantum computer has not yet been demonstrated. In this review, we point out that the quantum software and hardware systems should be designed collaboratively to fully exploit the potential of quantum computing. We first review three related works, including one hardware-aware quantum compiler optimization, one application-aware quantum hardware architecture design flow, and one co-design approach for the emerging quantum computational chemistry. Then we discuss some potential future directions following the co-design principle.
@article{10.1145/3477206.3477464, author = {Li, Gushu and Wu, Anbang and Shi, Yunong and Javadi-Abhari, Ali and Ding, Yufei and Xie, Yuan}, title = {On the Co-Design of Quantum Software and Hardware}, year = {2021}, isbn = {9781450387101}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3477206.3477464}, doi = {10.1145/3477206.3477464}, journal = {NANOCOM}, articleno = {15}, numpages = {7}, keywords = {quantum computing, software-hardware co-design, quantum compiler, superconducting quantum architecture}, location = {Virtual Event, Italy}, series = {NANOCOM '21}, } - ISCASoftware-Hardware Co-Optimization for Computational Chemistry on Superconducting Quantum ProcessorsGushu Li, Yunong Shi, and Ali Javadi-AbhariISCA, 2021
Computational chemistry is the leading application to demonstrate the advantage of quantum computing in the near term. However, large-scale simulation of chemical systems on quantum computers is currently hindered due to a mismatch between the computational resource needs of the program and those available in today’s technology. In this paper we argue that significant new optimizations can be discovered by co-designing the application, compiler, and hardware. We show that multiple optimization objectives can be coordinated through the key abstraction layer of Pauli strings, which are the basic building blocks of computational chemistry programs. In particular, we leverage Pauli strings to identify critical program components that can be used to compress program size with minimal loss of accuracy. We also leverage the structure of Pauli string simulation circuits to tailor a novel hardware architecture and compiler, leading to significant execution overhead reduction by up to 99%. While exploiting the high-level domain knowledge reveals significant optimization opportunities, our hardware/software framework is not tied to a particular program instance and can accommodate the full family of computational chemistry problems with such structure. We believe the co-design lessons of this study can be extended to other domains and hardware technologies to hasten the onset of quantum advantage.
@article{10.1109/ISCA52012.2021.00070, author = {Li, Gushu and Shi, Yunong and Javadi-Abhari, Ali}, title = {Software-Hardware Co-Optimization for Computational Chemistry on Superconducting Quantum Processors}, year = {2021}, isbn = {9781450390866}, publisher = {IEEE Press}, url = {https://doi.org/10.1109/ISCA52012.2021.00070}, doi = {10.1109/ISCA52012.2021.00070}, journal = {ISCA}, pages = {832–845}, numpages = {14}, keywords = {superconducting quantum processor, software-hardware co-optimization, computational chemistry, quantum computing}, location = {Virtual Event, Spain}, series = {ISCA '21}, } - ICRCOptimized Quantum Program Execution Ordering to Mitigate Errors in Simulations of Quantum SystemsTeague Tomesh, Kaiwen Gui, Pranav Gokhale, and 4 more authorsICRC, 2021
@article{9743179, author = {Tomesh, Teague and Gui, Kaiwen and Gokhale, Pranav and Shi, Yunong and Chong, Frederic T. and Martonosi, Margaret and Suchara, Martin}, journal = {ICRC}, title = {Optimized Quantum Program Execution Ordering to Mitigate Errors in Simulations of Quantum Systems}, year = {2021}, volume = {}, number = {}, pages = {1-13}, doi = {10.1109/ICRC53822.2021.00013}, }
2020
- MICROOptimized Quantum Compilation for Near-Term Algorithms with OpenPulsePranav Gokhale, Ali Javadi-Abhari, Nathan Earnest, and 2 more authorsMICRO, 2020
@article{9251970, author = {Gokhale, Pranav and Javadi-Abhari, Ali and Earnest, Nathan and Shi, Yunong and Chong, Frederic T.}, journal = {MICRO}, title = {Optimized Quantum Compilation for Near-Term Algorithms with OpenPulse}, year = {2020}, volume = {}, number = {}, pages = {186-200}, doi = {10.1109/MICRO50266.2020.00027}, } - PIEEEResource-Efficient Quantum Computing by Breaking AbstractionsYunong Shi, Pranav Gokhale, Prakash Murali, and 11 more authorsProceedings of the IEEE, 2020
Building a quantum computer that surpasses the computational power of its classical counterpart is a great engineering challenge. Quantum software optimizations can provide an accelerated pathway to the first generation of quantum computing applications that might save years of engineering effort. Current quantum software stacks follow a layered approach similar to the stack of classical computers, which was designed to manage the complexity. In this review, we point out that greater efficiency of quantum computing systems can be achieved by breaking the abstractions between these layers. We review several works along this line, including two hardware-aware compilation optimizations that break the quantum Instruction Set Architecture (ISA) abstraction and two error-correction/informationprocessing schemes that break the qubit abstraction. Last, we discuss several possible future directions.
@article{9116963, author = {Shi, Yunong and Gokhale, Pranav and Murali, Prakash and Baker, Jonathan M. and Duckering, Casey and Ding, Yongshan and Brown, Natalie C. and Chamberland, Christopher and Javadi-Abhari, Ali and Cross, Andrew W. and Schuster, David I. and Brown, Kenneth R. and Martonosi, Margaret and Chong, Frederic T.}, journal = {Proceedings of the IEEE}, title = {Resource-Efficient Quantum Computing by Breaking Abstractions}, year = {2020}, volume = {108}, number = {8}, pages = {1353-1370}, doi = {10.1109/JPROC.2020.2994765}, }
2019
- ASPLOSOptimized Compilation of Aggregated Instructions for Realistic Quantum ComputersYunong Shi, Nelson Leung, Pranav Gokhale, and 4 more authorsASPLOS, 2019
Recent developments in engineering and algorithms have made real-world applications in quantum computing possible in the near future. Existing quantum programming languages and compilers use a quantum assembly language composed of 1- and 2-qubit (quantum bit) gates. Quantum compiler frameworks translate this quantum assembly to electric signals (called control pulses) that implement the specified computation on specific physical devices. However, there is a mismatch between the operations defined by the 1- and 2-qubit logical ISA and their underlying physical implementation, so the current practice of directly translating logical instructions into control pulses results in inefficient, high-latency programs. To address this inefficiency, we propose a universal quantum compilation methodology that aggregates multiple logical operations into larger units that manipulate up to 10 qubits at a time. Our methodology then optimizes these aggregates by (1) finding commutative intermediate operations that result in more efficient schedules and (2) creating custom control pulses optimized for the aggregate (instead of individual 1- and 2-qubit operations). Compared to the standard gate-based compilation, the proposed approach realizes a deeper vertical integration of high-level quantum software and low-level, physical quantum hardware. We evaluate our approach on important near-term quantum applications on simulations of superconducting quantum architectures. Our proposed approach provides a mean speedup of 5times, with a maximum of 10times. Because latency directly affects the feasibility of quantum computation, our results not only improve performance but also have the potential to enable quantum computation sooner than otherwise possible.
@article{10.1145/3297858.3304018, author = {Shi, Yunong and Leung, Nelson and Gokhale, Pranav and Rossi, Zane and Schuster, David I. and Hoffmann, Henry and Chong, Frederic T.}, title = {Optimized Compilation of Aggregated Instructions for Realistic Quantum Computers}, year = {2019}, isbn = {9781450362405}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3297858.3304018}, doi = {10.1145/3297858.3304018}, journal = {ASPLOS}, pages = {1031–1044}, numpages = {14}, keywords = {quantum optimal control, compiler optimization, quantum computing}, location = {Providence, RI, USA}, series = {ASPLOS '19}, } - MICROPartial Compilation of Variational Algorithms for Noisy Intermediate-Scale Quantum MachinesPranav Gokhale, Yongshan Ding, Thomas Propson, and 6 more authorsIn , 2019
Quantum computing is on the cusp of reality with Noisy Intermediate-Scale Quantum (NISQ) machines currently under development and testing. Some of the most promising algorithms for these machines are variational algorithms that employ classical optimization coupled with quantum hardware to evaluate the quality of each candidate solution. Recent work used GRadient Descent Pulse Engineering (GRAPE) to translate quantum programs into highly optimized machine control pulses, resulting in a significant reduction in the execution time of programs. This is critical, as quantum machines can barely support the execution of short programs before failing.However, GRAPE suffers from high compilation latency, which is untenable in variational algorithms since compilation is interleaved with computation. We propose two strategies for partial compilation, exploiting the structure of variational circuits to pre-compile optimal pulses for specific blocks of gates. Our results indicate significant pulse speedups ranging from 1.5x-3x in typical benchmarks, with only a small fraction of the compilation latency of GRAPE.
@inproceedings{10.1145/3352460.3358313, author = {Gokhale, Pranav and Ding, Yongshan and Propson, Thomas and Winkler, Christopher and Leung, Nelson and Shi, Yunong and Schuster, David I. and Hoffmann, Henry and Chong, Frederic T.}, title = {Partial Compilation of Variational Algorithms for Noisy Intermediate-Scale Quantum Machines}, year = {2019}, isbn = {9781450369381}, publisher = {Association for Computing Machinery}, address = {New York, NY, USA}, url = {https://doi.org/10.1145/3352460.3358313}, doi = {10.1145/3352460.3358313}, journal = {MICRO}, pages = {266–278}, numpages = {13}, keywords = {variational algorithms, optimal control, quantum computing}, location = {Columbus, OH, USA}, series = {MICRO '52}, } - NJPFault-tolerant preparation of approximate GKP statesYunong Shi, Christopher Chamberland, and Andrew CrossNew Journal of Physics, Sep 2019
Gottesman–Kitaev–Preskill (GKP) states appear to be amongst the leading candidates for correcting errors when encoding qubits into oscillators. However the preparation of GKP states remains a significant theoretical and experimental challenge. Until now, no clear definitions for fault-tolerantly preparing GKP states have been provided. Without careful consideration, a small number of faults can lead to large uncorrectable shift errors. After proposing a metric to compare approximate GKP states, we provide rigorous definitions of fault-tolerance and introduce a fault-tolerant phase estimation protocol for preparing such states. The fault-tolerant protocol uses one flag qubit and accepts only a subset of states in order to prevent measurement readout errors from causing large shift errors. We then show how the protocol can be implemented using circuit QED. In doing so, we derive analytic expressions which describe the leading order effects of the nonlinear dispersive shift and Kerr nonlinearity. Using these expressions, we show that to mitigate the nonlinear dispersive shift and Kerr terms would require the protocol to be implemented on time scales four orders of magnitude longer than the time scales relevant to the protocol for physically motivated parameters. Despite these restrictions, we numerically show that a subset of the accepted states of the fault-tolerant phase estimation protocol maintain good error correcting capabilities even in the presence of noise.
@article{Shi_2019, author = {Shi, Yunong and Chamberland, Christopher and Cross, Andrew}, doi = {10.1088/1367-2630/ab3a62}, journal = {New Journal of Physics}, month = sep, number = {9}, pages = {093007}, publisher = {{IOP} Publishing}, title = {Fault-tolerant preparation of approximate {GKP} states}, url = {https://doi.org/10.1088/1367-2630/ab3a62}, volume = {21}, year = {2019}, bdsk-url-1 = {https://doi.org/10.1088/1367-2630/ab3a62}, }