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$.
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.
 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).
 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).
 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).
 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).
 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).
 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).
 J. Kececioglu and D. Sankoff ``Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement'' Algorithmica 13, 180–210 (1995).
 Samuel King, Eddie Schoute, and Hrishee Shastri, ``reversal-sort'' (2021).
 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).
 Torleiv Kløve ``Spheres of Permutations under the Infinity Norm–Permutations with limited displacement'' report (2008).
 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).
 Doug McClure and Jay Gambetta ``Quantum computation center opens'' report (2019).
 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).
 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).
 Thach Cam Nguyen, Hieu Trung Ngo, and Nguyen Bao Nguyen, ``Sorting by Restricted-Length-Weighted Reversals'' Genomics, Proteomics & Bioinformatics 3, 120–127 (2005).
 M. Pedram and A. Shafaei ``Layout Optimization for Quantum Circuits with Linear Nearest Neighbor Architectures'' IEEE Circuits and Systems Magazine 16, 62–74 (2016).
 Ron Pinter and Steven Skiena ``Genomic sorting with length-weighted reversals'' Genome informatics. International Conference on Genome Informatics 13, 103–11 (2002).
 Mehdi Saeedi, Robert Wille, and Rolf Drechsler, ``Synthesis of quantum circuits for linear nearest neighbor architectures'' Quantum Information Processing 10, 355–377 (2011).
 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).
 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).
 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).
 I. Tamo and M. Schwartz ``Correcting Limited-Magnitude Errors in the Rank-Modulation Scheme'' IEEE Transactions on Information Theory 56, 2551–2560 (2010).
 Cynthia Chen, Bruno Schmitt, Helena Zhang, Lev S. Bishop, and Ali Javadi-Abhar, Proceedings of the 59th ACM/IEEE Design Automation Conference 7 (2022) ISBN:9781450391429.
 Ferran Riera-Sàbat, Pavel Sekatski, and Wolfgang Dür, "A quantum simulator based on locally controlled logical systems", New Journal of Physics 25 2, 023001 (2023).
 Asim Sharma and Avah Banerjee, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 324 (2023) ISBN:979-8-3503-4323-6.
 Aniruddha Bapat, Andrew M. Childs, Alexey V. Gorshkov, and Eddie Schoute, "Advantages and Limitations of Quantum Routing", PRX Quantum 4 1, 010313 (2023).
 Asim Sharma and Avah Banerjee, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 82 (2023) ISBN:979-8-3503-4323-6.
The above citations are from Crossref's cited-by service (last updated successfully 2023-12-06 20:44:28) and SAO/NASA ADS (last updated successfully 2023-12-06 20:44:28). The list may be incomplete as not all publishers provide suitable and complete citation data.
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.