1Joint Center for Quantum Information and Computer Science, NIST/University of Maryland, College Park, Maryland 20742, USA
2Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland 20742, USA
3Department of Computer Science, University of Maryland, College Park, Maryland 20742, USA
4Joint Quantum Institute, NIST/University of Maryland, College Park, Maryland 20742, USA
5University of Rochester, Rochester, New York 14627, USA
6Reed College, Portland, Oregon 97202, USA
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
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 $epsilon approx 0.034$ such that the quantum routing time is at most $(1-epsilon)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 $2n/3$ in expectation for uniformly random permutations, whereas swap-based protocols require time $n$ asymptotically. Additionally, we consider sparse permutations that route $k le n$ qubits and give algorithms with quantum routing time at most $n/3 + O(k^2)$ on paths and at most $2r/3 + O(k^2)$ on general graphs with radius $r$.
Featured image: A bit string is split into three parts, each of which has the algorithm “TBS” applied to it but the middle part has TBS applied backwards. This results in three sorted bit strings, the left and right ascending, the middle descending. The three bit strings are joined and the part from the first 1 (from the left) to the last 0 is reversed, resulting in a sorted bit string.
Popular summary
In this paper we investigate how a novel primitive, called state reversal, can be used to perform quantum routing more quickly. Quantum routing is traditionally implemented using SWAP gates, which exchange two qubits. However, there is a protocol that uses nearest-neighbor quantum interactions to reverse the order of qubits on a path about three times faster than is possible using SWAP gates. We show how to use state reversal to implement an arbitrary permutation faster than is possible using SWAP gates. While the speedup is small (about 3%), this is the first such proven speedup that we are aware of for general routing. In the average case, we see even better performance: a factor-2/3 speedup over SWAP routing.
► BibTeX data
► References
[1] Noga Alon, F. R. K. Chung, and R. L. Graham, “Routing Permutations on Graphs via Matchings” SIAM Journal on Discrete Mathematics 7, 513-530 (1994).
https://doi.org/10.1137/s0895480192236628
[2] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis, “Quantum supremacy using a programmable superconducting processor” Nature 574, 505–510 (2019).
https://doi.org/10.1038/s41586-019-1666-5
[3] V. Bafna and P. A. Pevzner “Genome rearrangements and sorting by reversals” Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science 148–157 (1993).
https://doi.org/10.1137/S0097539793250627
[4] Indranil Banerjee and Dana Richards “New Results on Routing via Matchings on Graphs” Fundamentals of Computation Theory 69–81 (2017).
https://doi.org/10.1007/978-3-662-55751-8_7
[5] Aniruddha Bapat, Eddie Schoute, Alexey V. Gorshkov, and Andrew M. Childs, “Nearly optimal time-independent reversal of a spin chain” (2020).
arXiv:2003.02843v1
[6] Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter, Steven Skiena, and Firas Swidan, “Improved bounds on sorting by length-weighted reversals” Journal of Computer and System Sciences 74, 744–774 (2008).
https://doi.org/10.1016/j.jcss.2007.08.008
[7] C. H. Bennett, J. I. Cirac, M. S. Leifer, D. W. Leung, N. Linden, S. Popescu, and G. Vidal, “Optimal simulation of two-qubit Hamiltonians using general local operations” Physical Review A 66 (2002).
https://doi.org/10.1103/physreva.66.012305
[8] Teresa Brecht, Wolfgang Pfaff, Chen Wang, Yiwen Chu, Luigi Frunzio, Michel H. Devoret, and Robert J. Schoelkopf, “Multilayer microwave integrated quantum circuits for scalable quantum computing” npj Quantum Information 2 (2016).
https://doi.org/10.1038/npjqi.2016.2
[9] Andrew M. Childs, Eddie Schoute, and Cem M. Unsal, “Circuit Transformations for Quantum Architectures” 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019) 135, 3:1–3:24 (2019).
https://doi.org/10.4230/LIPIcs.TQC.2019.3
[10] J. Kececioglu and D. Sankoff “Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement” Algorithmica 13, 180–210 (1995).
https://doi.org/10.1007/BF01188586
[11] Samuel King, Eddie Schoute, and Hrishee Shastri, “reversal-sort” (2021).
https://gitlab.umiacs.umd.edu/amchilds/reversal-sort
[12] Morten Kjaergaard, Mollie E Schwartz, Jochen Braumüller, Philip Krantz, Joel I-J Wang, Simon Gustavsson, and William D Oliver, “Superconducting qubits: Current state of play” Annual Review of Condensed Matter Physics 11, 369–395 (2020).
https://doi.org/10.1146/annurev-conmatphys-031119-050605
[13] Torleiv Kløve “Spheres of Permutations under the Infinity Norm–Permutations with limited displacement” report (2008).
http://www.ii.uib.no/publikasjoner/texrap/pdf/2008-376.pdf
[14] S. Lakshmivarahan, Sudarshan K. Dhall, and Leslie L. Miller, “Parallel Sorting Algorithms” Elsevier (1984).
https://doi.org/10.1016/S0065-2458(08)60467-2
[15] Aaron Lye, Robert Wille, and Rolf Drechsler, “Determining the minimal number of swap gates for multi-dimensional nearest neighbor quantum circuits” The 20th Asia and South Pacific Design Automation Conference 178–183 (2015).
https://doi.org/10.1109/aspdac.2015.7059001
[16] Doug McClure and Jay Gambetta “Quantum computation center opens” report (2019).
https://www.ibm.com/blogs/research/2019/09/quantum-computation-center/
[17] C. Monroe and J. Kim “Scaling the Ion Trap Quantum Processor” Science 339, 1164–1169 (2013).
https://doi.org/10.1126/science.1231298
[18] C. Monroe, R. Raussendorf, A. Ruthven, K. R. Brown, P. Maunz, L.-M. Duan, and J. Kim, “Large-scale modular quantum-computer architecture with atomic memory and photonic interconnects” Physical Review A 89 (2014).
https://doi.org/10.1103/physreva.89.022317
[19] Prakash Murali, Jonathan M. Baker, Ali Javadi Abhari, Frederic T. Chong, and Margaret Martonosi, “Noise-Adaptive Compiler Mappings for Noisy Intermediate-Scale Quantum Computers” ASPLOS ’19 1015–1029 (2019).
https://doi.org/10.1145/3297858.3304075
[20] Thach Cam Nguyen, Hieu Trung Ngo, and Nguyen Bao Nguyen, “Sorting by Restricted-Length-Weighted Reversals” Genomics, Proteomics & Bioinformatics 3, 120–127 (2005).
https://doi.org/10.1016/S1672-0229(05)03016-0
[21] M. Pedram and A. Shafaei “Layout Optimization for Quantum Circuits with Linear Nearest Neighbor Architectures” IEEE Circuits and Systems Magazine 16, 62–74 (2016).
https://doi.org/10.1109/MCAS.2016.2549950
[22] Ron Pinter and Steven Skiena “Genomic sorting with length-weighted reversals” Genome informatics. International Conference on Genome Informatics 13, 103–11 (2002).
https://doi.org/10.11234/gi1990.13.103
[23] Robert Raussendorf “Quantum computation via translation-invariant operations on a chain of qubits” Physical Review A 72 (2005).
https://doi.org/10.1103/physreva.72.052301
[24] Herbert Robbins “A remark on Stirling’s formula” The American Mathematical Monthly 62, 26–29 (1955).
https://doi.org/10.2307/2315957
[25] Mehdi Saeedi, Robert Wille, and Rolf Drechsler, “Synthesis of quantum circuits for linear nearest neighbor architectures” Quantum Information Processing 10, 355–377 (2011).
https://doi.org/10.1007/s11128-010-0201-2
[26] M. Schwartz and P. O. Vontobel “Improved Lower Bounds on the Size of Balls Over Permutations With the Infinity Metric” IEEE Transactions on Information Theory 63, 6227–6239 (2017).
https://doi.org/10.1109/TIT.2017.2697423
[27] Alireza Shafaei, Mehdi Saeedi, and Massoud Pedram, “Optimization of Quantum Circuits for Interaction Distance in Linear Nearest Neighbor Architectures” Proceedings of the 50th Annual Design Automation Conference 41:1–41:6 (2013).
https://doi.org/10.1145/2463209.2488785
[28] Alireza Shafaei, Mehdi Saeedi, and Massoud Pedram, “Qubit placement to minimize communication overhead in 2D quantum architectures” 2014 19th Asia and South Pacific Design Automation Conference (ASP-DAC) (2014).
https://doi.org/10.1109/aspdac.2014.6742940
[29] I. Tamo and M. Schwartz “Correcting Limited-Magnitude Errors in the Rank-Modulation Scheme” IEEE Transactions on Information Theory 56, 2551–2560 (2010).
https://doi.org/10.1109/TIT.2010.2046241
[30] G. Vidal, K. Hammerer, and J. I. Cirac, “Interaction Cost of Nonlocal Gates” Physical Review Letters 88, 237902 (2002).
https://doi.org/10.1103/PhysRevLett.88.237902
[31] Louxin Zhang “Optimal Bounds for Matching Routing on Trees” SIAM Journal on Discrete Mathematics 12, 64–77 (1999).
https://doi.org/10.1137/s0895480197323159
[32] Alwin Zulehner and Robert Wille “Compiling SU(4) quantum circuits to IBM QX architectures” ASP-DAC ’19 185–190 (2019).
https://doi.org/10.1145/3287624.3287704
Cited by
[1] Giacomo Nannicini, Lev S Bishop, Oktay Gunluk, and Petar Jurcevic, “Optimal qubit assignment and routing via integer programming”, arXiv:2106.06446.
The above citations are from SAO/NASA ADS (last updated successfully 2021-08-31 16:18:48). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2021-08-31 16:18:46: Could not fetch cited-by data for 10.22331/q-2021-08-31-533 from Crossref. This is normal if the DOI was registered recently.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.
Source: https://quantum-journal.org/papers/q-2021-08-31-533/
