More Like this

1. Asymptotic improvements to quantum circuits via qutrits

   https://doi.org/10.1145/3307650.3322253  

   Gokhale, Pranav ; Baker, Jonathan M. ; Duckering, Casey ; Brown, Natalie C. ; Brown, Kenneth R. ; Chong, Frederic T. ( June 2019 , ISCA '19 Proceedings of the 46th International Symposium on Computer Architecture)

   Quantum computation is traditionally expressed in terms of quantum bits, or qubits. In this work, we instead consider three-level qutrits. Past work with qutrits has demonstrated only constant factor improvements, owing to the log2(3) binary-to-ternary compression factor. We present a novel technique using qutrits to achieve a logarithmic depth (runtime) decomposition of the Generalized Toffoli gate using no ancilla-a significant improvement over linear depth for the best qubit-only equivalent. Our circuit construction also features a 70x improvement in two-qudit gate count over the qubit-only equivalent decomposition. This results in circuit cost reductions for important algorithms like quantum neurons and Grover search. We develop an open-source circuit simulator for qutrits, along with realistic near-term noise models which account for the cost of operating qutrits. Simulation results for these noise models indicate over 90% mean reliability (fidelity) for our circuit construction, versus under 30% for the qubit-only baseline. These results suggest that qutrits offer a promising path towards scaling quantum computation. 

   more » « less
2. Spacetime-Efficient Low-Depth Quantum State Preparation with Applications

   https://doi.org/10.22331/q-2024-02-15-1257  

   Gui, Kaiwen ; Dalzell, Alexander M. ; Achille, Alessandro ; Suchara, Martin ; Chong, Frederic T. ( February 2024 , Quantum)

   We propose a novel deterministic method for preparing arbitrary quantum states. When our protocol is compiled into CNOT and arbitrary single-qubit gates, it prepares an$N$-dimensional state in depth$O(\log (N))$and$\mathit{\text{spacetime allocation}}$(a metric that accounts for the fact that oftentimes some ancilla qubits need not be active for the entire circuit)$O(N)$, which are both optimal. When compiled into the$\{\mathrm{H},\mathrm{S},\mathrm{T},\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}\}$gate set, we show that it requires asymptotically fewer quantum resources than previous methods. Specifically, it prepares an arbitrary state up to error$ϵ$with optimal depth of$O(\log (N)+\log (1/ϵ))$and spacetime allocation$O(N\log (\log (N)/ϵ))$, improving over$O(\log (N)\log (\log (N)/ϵ))$and$O(N\log (N/ϵ))$, respectively. We illustrate how the reduced spacetime allocation of our protocol enables rapid preparation of many disjoint states with only constant-factor ancilla overhead –$O(N)$ancilla qubits are reused efficiently to prepare a product state of$w$$N$-dimensional states in depth$O(w+\log (N))$rather than$O(w\log (N))$, achieving effectively constant depth per state. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations. We provide quantum circuit descriptions of our protocol, detailed pseudocode, and gate-level implementation examples using Braket.

    

   more » « less
3. SQUARE: Strategic Quantum Ancilla Reuse for Modular Quantum Programs via Cost-Effective Uncomputation

   Ding, Yongshan ; Wu, Xin-Chuan ; Holmes, Adam ; Wiseth, Ash ; Franklin, Diana ; Martonosi, Margaret ; and Chong, Frederic T. ( June 2020 , ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA))

   Compiling high-level quantum programs to machines that are size constrained (i.e. limited number of quantum bits) and time constrained (i.e. limited number of quantum operations) is challenging. In this paper, we present SQUARE (Strategic QUantum Ancilla REuse), a compilation infrastructure that tackles allocation and reclamation of scratch qubits (called ancilla) in modular quantum programs. At its core, SQUARE strategically performs uncomputation to create opportunities for qubit reuse. Current Noisy Intermediate-Scale Quantum (NISQ) computers and forward-looking Fault-Tolerant (FT) quantum computers have fundamentally different constraints such as data locality, instruction parallelism, and communication overhead. Our heuristic-based ancilla-reuse algorithm balances these considerations and fits computations into resource-constrained NISQ or FT quantum machines, throttling parallelism when necessary. To precisely capture the workload of a program, we propose an improved metric, the "active quantum volume," and use this metric to evaluate the effectiveness of our algorithm. Our results show that SQUARE improves the average success rate of NISQ applications by 1.47X. Surprisingly, the additional gates for uncomputation create ancilla with better locality, and result in substantially fewer swap gates and less gate noise overall. SQUARE also achieves an average reduction of 1.5X (and up to 9.6X) in active quantum volume for FT machines. 

   more » « less
4. Just-in-time Quantum Circuit Transpilation Reduces Noise

   Ellis Wilson, Sudhakar Singh ( October 2020 , International Conference on Quantum Computing and Engineering (QCE))

   Running quantum programs is fraught with challenges on on today’s noisy intermediate scale quantum (NISQ) devices. Many of these challenges originate from the error characteristics that stem from rapid decoherence and noise during measurement, qubit connections, crosstalk, the qubits themselves, and transformations of qubit state via gates. Not only are qubits not “created equal”, but their noise level also changes over time. IBM is said to calibrate their quantum systems once per day and reports noise levels (errors) at the time of such calibration. This information is subsequently used to map circuits to higher quality qubits and connections up to the next calibration point. This work provides evidence that there is room for improvement over this daily calibration cycle. It contributes a technique to measure noise levels (errors) related to qubits immediately before executing one or more sensitive circuits and shows that just-in-time noise measurements can benefit late physical qubit mappings. With this just-in-time recalibrated transpilation, the fidelity of results is improved over IBM’s default mappings, which only uses their daily calibrations. The framework assess two major sources of noise, namely readout errors (measurement errors) and two-qubit gate/connection errors. Experiments indicate that the accuracy of circuit results improves by 3-304% on average and up to 400% with on-the-fly circuit mappings based on error measurements just prior to application execution. 

   more » « less
5. A quantum hamiltonian simulation benchmark

   https://doi.org/10.1038/s41534-022-00636-x  

   Dong, Yulong ; Whaley, K. Birgitta ; Lin, Lin ( December 2022 , npj Quantum Information)

   Abstract Hamiltonian simulation is one of the most important problems in quantum computation, and quantum singular value transformation (QSVT) is an efficient way to simulate a general class of Hamiltonians. However, the QSVT circuit typically involves multiple ancilla qubits and multi-qubit control gates. In order to simulate a certain class of n -qubit random Hamiltonians, we propose a drastically simplified quantum circuit that we refer to as the minimal QSVT circuit, which uses only one ancilla qubit and no multi-qubit controlled gates. We formulate a simple metric called the quantum unitary evolution score (QUES), which is a scalable quantum benchmark and can be verified without any need for classical computation. Under the globally depolarized noise model, we demonstrate that QUES is directly related to the circuit fidelity, and the potential classical hardness of an associated quantum circuit sampling problem. Under the same assumption, theoretical analysis suggests there exists an ‘optimal’ simulation time t opt  ≈ 4.81, at which even a noisy quantum device may be sufficient to demonstrate the potential classical hardness. 

   more » « less