More Like this

1. Not All SWAPs Have the Same Cost: A Case for Optimization-Aware Qubit Routing

   https://doi.org/10.1109/HPCA53966.2022.00058  

   Liu, Ji ; Li, Peiyi ; Zhou, Huiyang ( April 2022 , 2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA))

   Despite rapid advances in quantum computing technologies, the qubit connectivity limitation remains to be a critical challenge. Both near-term NISQ quantum computers and relatively long-term scalable quantum architectures do not offer full connectivity. As a result, quantum circuits may not be directly executed on quantum hardware, and a quantum compiler needs to perform qubit routing to make the circuit compatible with the device layout. During the qubit routing step, the compiler inserts SWAP gates and performs circuit transformations. Given the connectivity topology of the target hardware, there are typically multiple qubit routing candidates. The state-of-the-art compilers use a cost function to evaluate the number of SWAP gates for different routes and then select the one with the minimum number of SWAP gates. After qubit routing, the quantum compiler performs gate optimizations upon the circuit with the newly inserted SWAP gates. In this paper, we observe that the aforementioned qubit routing is not optimal, and qubit routing should not be independent on subsequent gate optimizations. We find that with the consideration of gate optimizations, not all of the SWAP gates have the same basis-gate cost. These insights lead to the development of our qubit routing algorithm, NASSC (Not All Swaps have the Same Cost). NASSC is the first algorithm that considers the subsequent optimizations during the routing step. Our optimization-aware qubit routing leads to better routing decisions and benefits subsequent optimizations. We also propose a new optimization-aware decomposition for the inserted SWAP gates. Our experiments show that the routing overhead compiled with our routing algorithm is reduced by up to 69.30% (21.30% on average) in the number of CNOT gates and up to 43.50% (7.61% on average) in the circuit depth compared with the state-of-the-art scheme, SABRE. 

   more » « less
2. Quantum routing with fast reversals

   https://doi.org/10.22331/q-2021-08-31-533  

   Bapat, Aniruddha ; Childs, Andrew M. ; Gorshkov, Alexey V. ; King, Samuel ; Schoute, Eddie ; Shastri, Hrishee ( August 2021 , Quantum)

   null (Ed.)

   We present methods for implementing arbitrary permutations of qubits under interaction constraints. Our protocols make use of previous methods for rapidly reversing the order of qubits along a path. Given nearest-neighbor interactions on a path of length n , we show that there exists a constant ϵ ≈ 0.034 such that the quantum routing time is at most ( 1 − ϵ ) n , whereas any swap-based protocol needs at least time n − 1 . This represents the first known quantum advantage over swap-based routing methods and also gives improved quantum routing times for realistic architectures such as grids. Furthermore, we show that our algorithm approaches a quantum routing time of 2 n / 3 in expectation for uniformly random permutations, whereas swap-based protocols require time n asymptotically. Additionally, we consider sparse permutations that route k ≤ n qubits and give algorithms with quantum routing time at most n / 3 + O ( k 2 ) on paths and at most 2 r / 3 + O ( k 2 ) on general graphs with radius r . 

   more » « less
3. DigiQ: A Scalable Digital Controller for Quantum Computers Using SFQ Logic

   https://doi.org/10.1109/HPCA53966.2022.00037  

   Jokar, Mohammad Reza ; Rines, Richard ; Pasandi, Ghasem ; Cong, Haolin ; Holmes, Adam ; Shi, Yunong ; Pedram, Massoud ; Chong, Frederic T. ( April 2022 , 2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA))

   The control of cryogenic qubits in today’s super-conducting quantum computer prototypes presents significant scalability challenges due to the massive costs of generating/routing the analog control signals that need to be sent from a classical controller at room temperature to the quantum chip inside the dilution refrigerator. Thus, researchers in industry and academia have focused on designing in-fridge classical controllers in order to mitigate these challenges. Due to the maturity of CMOS logic, many industrial efforts (Microsoft, Intel) have focused on Cryo-CMOS as a near-term solution to design in-fridge classical controllers. Meanwhile, Supercon-ducting Single Flux Quantum (SFQ) is an alternative, less mature classical logic family proposed for large-scale in-fridge controllers. SFQ logic has the potential to maximize scalability thanks to its ultra-high speed and very low power consumption. However, architecture design for SFQ logic poses challenges due to its unconventional pulse-driven nature and lack of dense memory and logic. Thus, research at the architecture level is essential to guide architects to design SFQ-based classical controllers for large-scale quantum machines.In this paper, we present DigiQ, the first system-level design of a Noisy Intermediate Scale Quantum (NISQ)-friendly SFQ-based classical controller. We perform a design space exploration of SFQ-based controllers and co-design the quantum gate decompositions and SFQ-based implementation of those decompositions to find an optimal SFQ-friendly design point that trades area and power for latency and control while ensuring good quantum algorithmic performance. Our co-design results in a single instruction, multiple data (SIMD) controller architecture, which has high scalability, but imposes new challenges on the calibration of control pulses. We present software-level solutions to address these challenges, which if unaddressed would degrade quantum circuit fidelity given the imperfections of qubit hardware.To validate and characterize DigiQ, we first implement it using hardware description languages and synthesize it using state-of-the-art/validated SFQ synthesis tools. Our synthesis results show that DigiQ can operate within the tight power and area budget of dilution refrigerators at >42,000-qubit scales. Second, we confirm the effectiveness of DigiQ in running quantum algorithms by modeling the execution time and fidelity of a variety of NISQ applications. We hope that the promising results of this paper motivate experimentalists to further explore SFQ-based quantum controllers to realize large-scale quantum machines with maximized scalability. 

   more » « less
4. Practical implications of SFQ-based two-qubit gates

   https://doi.org/10.1109/QCE52317.2021.00061  

   Jokar, Mohammad Reza ; Rines, Richard ; Chong, Frederic T. ( October 2021 , 2021 IEEE International Conference on Quantum Computing and Engineering (QCE))

   Scalability of today’s superconducting quantum computers is limited due to the huge costs of generating/routing microwave control pulses per qubit from room temperature. One active research area in both industry and academia is to push the classical controllers to the dilution refrigerator in order to increase the scalability of quantum computers. Superconducting Single Flux Quantum (SFQ) is a classical logic technology with low power consumption and ultra-high speed, and thus is a promising candidate for in-fridge classical controllers with maximized scalability. Prior work has demonstrated high-fidelity SFQ-based single-qubit gates. However, little research has been done on SFQ-based multi-qubit gates, which are necessary to realize SFQ-based universal quantum computing.In this paper, we present the first thorough analysis of SFQ-based two-qubit gates. Our observations show that SFQ-based two-qubit gates tend to have high leakage to qubit non-computational subspace, which presents severe design challenges. We show that despite these challenges, we can realize gates with high fidelity by carefully designing optimal control methods and qubit architectures. We develop optimal control methods that suppress leakage, and also investigate various qubit architectures that reduce the leakage. After carefully engineering our SFQ-friendly quantum system, we show that it can achieve similar gate fidelity and gate time to microwave-based quantum systems. The promising results of this paper show that (1) SFQ-based universal quantum computation is both feasible and effective; and (2) SFQ is a promising approach in designing classical controller for quantum machines because it can increase the scalability while preserving gate fidelity and performance. 

   more » « less
5. Random Quantum Circuits Transform Local Noise into Global White Noise

   https://doi.org/10.1007/s00220-024-04958-z  

   Dalzell, Alexander M. ; Hunter-Jones, Nicholas ; Brandão, Fernando G. S. L. ( March 2024 , Communications in Mathematical Physics)

   We study the distribution over measurement outcomes of noisy random quantum circuits in the regime of low fidelity, which corresponds to the setting where the computation experiences at least one gate-level error with probability close to one. We model noise by adding a pair of weak, unital, single-qubit noise channels after each two-qubit gate, and we show that for typical random circuit instances, correlations between the noisy output distribution$$p_{\text {noisy}}$$$p_{\text{noisy}}$and the corresponding noiseless output distribution$$p_{\text {ideal}}$$$p_{\text{ideal}}$shrink exponentially with the expected number of gate-level errors. Specifically, the linear cross-entropy benchmarkFthat measures this correlation behaves as$$F=\text {exp}(-2s\epsilon \pm O(s\epsilon ^2))$$$F=\text{exp}(-2sϵ\pm O\left(s{ϵ}^2\right))$, where$$\epsilon $$$ϵ$is the probability of error per circuit location andsis the number of two-qubit gates. Furthermore, if the noise is incoherent—for example, depolarizing or dephasing noise—the total variation distance between the noisy output distribution$$p_{\text {noisy}}$$$p_{\text{noisy}}$and the uniform distribution$$p_{\text {unif}}$$$p_{\text{unif}}$decays at precisely the same rate. Consequently, the noisy output distribution can be approximated as$$p_{\text {noisy}}\approx Fp_{\text {ideal}}+ (1-F)p_{\text {unif}}$$$p_{\text{noisy}}\approx F{p}_{\text{ideal}}+(1-F)p_{\text{unif}}$. In other words, although at least one local error occurs with probability$$1-F$$$1-F$, the errors are scrambled by the random quantum circuit and can be treated as global white noise, contributing completely uniform output. Importantly, we upper bound the average total variation error in this approximation by$$O(F\epsilon \sqrt{s})$$$O\left(Fϵ\sqrt{s}\right)$. Thus, the “white-noise approximation” is meaningful when$$\epsilon \sqrt{s} \ll 1$$$ϵ\sqrt{s}\ll 1$, a quadratically weaker condition than the$$\epsilon s\ll 1$$$ϵs\ll 1$requirement to maintain high fidelity. The bound applies if the circuit size satisfies$$s \ge \Omega (n\log (n))$$$s\ge \Omega (nlog(n\left)\right)$, which corresponds to onlylogarithmic depthcircuits, and if, additionally, the inverse error rate satisfies$$\epsilon ^{-1} \ge {\tilde{\Omega }}(n)$$${ϵ}^{-1}\ge \tilde{\Omega }\left(n\right)$, which is needed to ensure errors are scrambled faster thanFdecays. The white-noise approximation is useful for salvaging the signal from a noisy quantum computation; for example, it was an underlying assumption in complexity-theoretic arguments that noisy random quantum circuits cannot be efficiently sampled classically, even when the fidelity is low. Our method is based on a map from second-moment quantities in random quantum circuits to expectation values of certain stochastic processes for which we compute upper and lower bounds.

    

   more » « less