乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,21]],"date-time":"2024-07-21T05:16:47Z","timestamp":1721539007878},"reference-count":32,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T00:00:00Z","timestamp":1630368000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"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<\/mml:mi><\/mml:math>, we show that there exists a constant \u03f5<\/mml:mi>\u2248<\/mml:mo>0.034<\/mml:mn><\/mml:math> such that the quantum routing time is at most (<\/mml:mo>1<\/mml:mn>\u2212<\/mml:mo>\u03f5<\/mml:mi>)<\/mml:mo>n<\/mml:mi><\/mml:math>, whereas any swap-based protocol needs at least time n<\/mml:mi>\u2212<\/mml:mo>1<\/mml:mn><\/mml:math>. 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<\/mml:mn>n<\/mml:mi>\/<\/mml:mo><\/mml:mrow>3<\/mml:mn><\/mml:math> in expectation for uniformly random permutations, whereas swap-based protocols require time n<\/mml:mi><\/mml:math> asymptotically. Additionally, we consider sparse permutations that route k<\/mml:mi>\u2264<\/mml:mo>n<\/mml:mi><\/mml:math> qubits and give algorithms with quantum routing time at most n<\/mml:mi>\/<\/mml:mo><\/mml:mrow>3<\/mml:mn>+<\/mml:mo>O<\/mml:mi>(<\/mml:mo>k<\/mml:mi>2<\/mml:mn><\/mml:msup>)<\/mml:mo><\/mml:math> on paths and at most 2<\/mml:mn>r<\/mml:mi>\/<\/mml:mo><\/mml:mrow>3<\/mml:mn>+<\/mml:mo>O<\/mml:mi>(<\/mml:mo>k<\/mml:mi>2<\/mml:mn><\/mml:msup>)<\/mml:mo><\/mml:math> on general graphs with radius r<\/mml:mi><\/mml:math>.<\/jats:p>","DOI":"10.22331\/q-2021-08-31-533","type":"journal-article","created":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T17:46:58Z","timestamp":1630432018000},"page":"533","update-policy":"http:\/\/dx.doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":8,"title":["Quantum routing with fast reversals"],"prefix":"10.22331","volume":"5","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-9489-9165","authenticated-orcid":false,"given":"Aniruddha","family":"Bapat","sequence":"first","affiliation":[{"name":"Joint Center for Quantum Information and Computer Science, NIST\/University of Maryland, College Park, Maryland 20742, USA"},{"name":"Joint Quantum Institute, NIST\/University of Maryland, College Park, Maryland 20742, USA"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-9903-837X","authenticated-orcid":false,"given":"Andrew M.","family":"Childs","sequence":"additional","affiliation":[{"name":"Joint Center for Quantum Information and Computer Science, NIST\/University of Maryland, College Park, Maryland 20742, USA"},{"name":"Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland 20742, USA"},{"name":"Department of Computer Science, University of Maryland, College Park, Maryland 20742, USA"}]},{"ORCID":"http:\/\/orcid.org\/0000-0003-0509-3421","authenticated-orcid":false,"given":"Alexey V.","family":"Gorshkov","sequence":"additional","affiliation":[{"name":"Joint Center for Quantum Information and Computer Science, NIST\/University of Maryland, College Park, Maryland 20742, USA"},{"name":"Joint Quantum Institute, NIST\/University of Maryland, College Park, Maryland 20742, USA"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-9575-9225","authenticated-orcid":false,"given":"Samuel","family":"King","sequence":"additional","affiliation":[{"name":"University of Rochester, Rochester, New York 14627, USA"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-5613-1443","authenticated-orcid":false,"given":"Eddie","family":"Schoute","sequence":"additional","affiliation":[{"name":"Joint Center for Quantum Information and Computer Science, NIST\/University of Maryland, College Park, Maryland 20742, USA"},{"name":"Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland 20742, USA"},{"name":"Department of Computer Science, University of Maryland, College Park, Maryland 20742, USA"}]},{"ORCID":"http:\/\/orcid.org\/0000-0002-6188-1572","authenticated-orcid":false,"given":"Hrishee","family":"Shastri","sequence":"additional","affiliation":[{"name":"Reed College, Portland, Oregon 97202, USA"}]}],"member":"9598","published-online":{"date-parts":[[2021,8,31]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1137\/s0895480192236628"},{"key":"1","doi-asserted-by":"publisher","unstructured":"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\u00e0, 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\u2013510 (2019).","DOI":"10.1038\/s41586-019-1666-5"},{"key":"2","doi-asserted-by":"publisher","unstructured":"V. Bafna and P. A. Pevzner ``Genome rearrangements and sorting by reversals'' Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science 148\u2013157 (1993).","DOI":"10.1137\/S0097539793250627"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Indranil Banerjee and Dana Richards ``New Results on Routing via Matchings on Graphs'' Fundamentals of Computation Theory 69\u201381 (2017).","DOI":"10.1007\/978-3-662-55751-8_7"},{"key":"4","unstructured":"Aniruddha Bapat, Eddie Schoute, Alexey V. Gorshkov, and Andrew M. Childs, ``Nearly optimal time-independent reversal of a spin chain'' (2020)."},{"key":"5","doi-asserted-by":"publisher","unstructured":"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\u2013774 (2008).","DOI":"10.1016\/j.jcss.2007.08.008"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/physreva.66.012305"},{"key":"7","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/npjqi.2016.2"},{"key":"8","doi-asserted-by":"publisher","unstructured":"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\u20133:24 (2019).","DOI":"10.4230\/LIPIcs.TQC.2019.3"},{"key":"9","doi-asserted-by":"publisher","unstructured":"J. Kececioglu and D. Sankoff ``Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement'' Algorithmica 13, 180\u2013210 (1995).","DOI":"10.1007\/BF01188586"},{"key":"10","unstructured":"Samuel King, Eddie Schoute, and Hrishee Shastri, ``reversal-sort'' (2021)."},{"key":"11","doi-asserted-by":"publisher","unstructured":"Morten Kjaergaard, Mollie E Schwartz, Jochen Braum\u00fcller, 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\u2013395 (2020).","DOI":"10.1146\/annurev-conmatphys-031119-050605"},{"key":"12","doi-asserted-by":"crossref","unstructured":"Torleiv Kl\u00f8ve ``Spheres of Permutations under the Infinity Norm\u2013Permutations with limited displacement'' report (2008).","DOI":"10.37236\/193"},{"key":"13","doi-asserted-by":"publisher","unstructured":"S. Lakshmivarahan, Sudarshan K. Dhall, and Leslie L. Miller, ``Parallel Sorting Algorithms'' Elsevier (1984).","DOI":"10.1016\/S0065-2458(08)60467-2"},{"key":"14","doi-asserted-by":"publisher","unstructured":"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\u2013183 (2015).","DOI":"10.1109\/aspdac.2015.7059001"},{"key":"15","unstructured":"Doug McClure and Jay Gambetta ``Quantum computation center opens'' report (2019)."},{"key":"16","doi-asserted-by":"publisher","unstructured":"C. Monroe and J. Kim ``Scaling the Ion Trap Quantum Processor'' Science 339, 1164\u20131169 (2013).","DOI":"10.1126\/science.1231298"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/physreva.89.022317"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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\u20131029 (2019).","DOI":"10.1145\/3297858.3304075"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Thach Cam Nguyen, Hieu Trung Ngo, and Nguyen Bao Nguyen, ``Sorting by Restricted-Length-Weighted Reversals'' Genomics, Proteomics & Bioinformatics 3, 120\u2013127 (2005).","DOI":"10.1016\/S1672-0229(05)03016-0"},{"key":"20","doi-asserted-by":"publisher","unstructured":"M. Pedram and A. Shafaei ``Layout Optimization for Quantum Circuits with Linear Nearest Neighbor Architectures'' IEEE Circuits and Systems Magazine 16, 62\u201374 (2016).","DOI":"10.1109\/MCAS.2016.2549950"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Ron Pinter and Steven Skiena ``Genomic sorting with length-weighted reversals'' Genome informatics. International Conference on Genome Informatics 13, 103\u201311 (2002).","DOI":"10.11234\/gi1990.13.103"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Robert Raussendorf ``Quantum computation via translation-invariant operations on a chain of qubits'' Physical Review A 72 (2005).","DOI":"10.1103\/physreva.72.052301"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Herbert Robbins ``A remark on Stirling's formula'' The American Mathematical Monthly 62, 26\u201329 (1955).","DOI":"10.2307\/2315957"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Mehdi Saeedi, Robert Wille, and Rolf Drechsler, ``Synthesis of quantum circuits for linear nearest neighbor architectures'' Quantum Information Processing 10, 355\u2013377 (2011).","DOI":"10.1007\/s11128-010-0201-2"},{"key":"25","doi-asserted-by":"publisher","unstructured":"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\u20136239 (2017).","DOI":"10.1109\/TIT.2017.2697423"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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\u201341:6 (2013).","DOI":"10.1145\/2463209.2488785"},{"key":"27","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1109\/aspdac.2014.6742940"},{"key":"28","doi-asserted-by":"publisher","unstructured":"I. Tamo and M. Schwartz ``Correcting Limited-Magnitude Errors in the Rank-Modulation Scheme'' IEEE Transactions on Information Theory 56, 2551\u20132560 (2010).","DOI":"10.1109\/TIT.2010.2046241"},{"key":"29","doi-asserted-by":"publisher","unstructured":"G. Vidal, K. Hammerer, and J. I. Cirac, ``Interaction Cost of Nonlocal Gates'' Physical Review Letters 88, 237902 (2002).","DOI":"10.1103\/PhysRevLett.88.237902"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Louxin Zhang ``Optimal Bounds for Matching Routing on Trees'' SIAM Journal on Discrete Mathematics 12, 64\u201377 (1999).","DOI":"10.1137\/s0895480197323159"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Alwin Zulehner and Robert Wille ``Compiling SU(4) quantum circuits to IBM QX architectures'' ASP-DAC '19 185\u2013190 (2019).","DOI":"10.1145\/3287624.3287704"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-08-31-533\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T17:47:06Z","timestamp":1630432026000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2021-08-31-533\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,31]]},"references-count":32,"URL":"https:\/\/doi.org\/10.22331\/q-2021-08-31-533","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,31]]},"article-number":"533"}}