Marcos Yukio Siraichi
Fernando Magno Quintao Pereira
ABSTRACT
In May of 2016, IBM Research has made a quantum processor available in the cloud to the general public. The possibility of programming an actual quantum device has elicited much enthusiasm. Yet, quantum programming still lacks the compiler support that modern programming languages enjoy today. To use universal quantum computers like IBM's, programmers must design low-level circuits. In particular, they must map logical qubits into physical qubits that need to obey connectivity constraints. This task resembles the early days of programming, in which software was built in machine languages. In this paper, we formally introduce the qubit allocation problem and provide an exact solution to it. This optimal algorithm deals with the simple quantum machinery available today; however, it cannot scale up to the more complex architectures scheduled to appear. Thus, we also provide a heuristic solution to qubit allocation, which is faster than the current solutions already implemented to deal with this problem.
- Steven Balensiefer, Lucas Kregor-Stickles, and Mark Oskin. 2005. An Evaluation Framework and Instruction Set Architecture for Ion-Trap Based Quantum Micro-Architectures. In ISCA. IEEE, Washington, DC, USA, 186-196. Google Scholar
Digital Library
- Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter. 1995. Elementary gates for quantum computation. Physical review A 52, 5 (1995), 3457.Google Scholar
- Richard Bellman. 1958. On a Routing Problem. Quart. Appl. Math. 16 (1958), 87-90.Google ScholarCross Ref
- Paul Benioff. 1980. The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. Journal of Statistical Physics 22, 5 (1980), 563-591.Google ScholarCross Ref
- Édouard Bonnet, Tillmann Miltzow, and Pawel Rzazewski. 2016. Complexity of Token Swapping and its Variants. CoRR arXiv:1607.07676, Article 2 (2016), 23 pages.Google Scholar
- Gregory J. Chaitin, Mark A. Auslander, Ashok K. Chandra, John Cocke, Martin E. Hopkins, and Peter W. Markstein. 1981. Register allocation via coloring. Computer Languages 6 (1981), 47-57. Google ScholarDigital Library
- Josep M Codina, Jesús Sánchez, and Antonio González. 2001. A unified modulo scheduling and register allocation technique for clustered processors. In Parallel Architectures and Compilation Techniques. IEEE, Los Alamitos, CA, USA, 175-184. Google ScholarDigital Library
- Stephen A. Cook. 1971. The Complexity of Theorem-proving Procedures. In STOC. ACM, New York, NY, USA, 151-158. Google ScholarDigital Library
- Andrew W. Cross, Lev S. Bishop, John A. Smolin, and Jay M. Gambetta. 2017. Open Quantum Assembly Language. IBM, Armonk, NY, USA.Google Scholar
- D. Deutsch. 1985. Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer. Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 400, 1818 (1985), 97-117.Google ScholarCross Ref
- Simon J. Devitt. 2016. Performing quantum computing experiments in the cloud. Phys. Rev. A 94, 3 (2016), 032329.Google ScholarCross Ref
- Michel H Devoret, Andreas Wallraff, and John M Martinis. 2004. Superconducting qubits: A short review. arXiv cond-mat/0411174 (2004), 1-41.Google Scholar
- Martin Farach and Vincenzo Liberatore. 1998. On local register allocation. In SODA. ACM, New York, NY, USA, 564-573. Google ScholarDigital Library
- Jay M Gambetta, Jerry M Chow, and Matthias Steffen. 2017. Building logical qubits in a superconducting quantum computing system. NPJ Quantum Mechanics 3, Article 2 (2017), 7 pages.Google Scholar
- Simon J Gay. 2006. Quantum programming languages: Survey and bibliography. Mathematical Structures in Computer Science 16, 4 (2006), 581-600. Google ScholarDigital Library
- Dario Gil. 2017. The Future of Computing: AI and Quantum. Online video.Google Scholar
- Alexander S Green, Peter LeFanu Lumsdaine, Neil J Ross, Peter Selinger, and Benoît Valiron. 2013. Quipper: a scalable quantum programming language. In SIGPLAN Notices, Vol. 48. ACM, New York, NY, USA, 333-342. Google ScholarDigital Library
- Lov K. Grover. 1996. A Fast Quantum Mechanical Algorithm for Database Search. In STOC. ACM, New York, NY, USA, 212-219. Google ScholarDigital Library
- Thomas Häner, Damian S. Steiger, Krysta M. Svore, and Matthias Troyer. 2016. A Software Methodology for Compiling Quantum Programs. CoRR abs/1604.01401 (2016), 1-14.Google Scholar
- Ali Javadi-Abhari, Pranav Gokhale, Adam Holmes, Diana Franklin, Kenneth R. Brown, Margaret Martonosi, and Frederic T. Chong. 2017. Optimized Surface Code Communication in Superconducting Quantum Computers. In MICRO. ACM, New York, NY, USA, 692-705. Google ScholarDigital Library
- Ali Javadi-Abhari, Shruti Patil, Daniel Kudrow, Jeff Heckey, Alexey Lvov, Frederic T Chong, and Margaret Martonosi. 2014. ScaffCC: a framework for compilation and analysis of quantum computing programs. In Computing Frontiers. ACM, New York, NY, USA, 1. Google ScholarDigital Library
- Jun Kawahara, Toshiki Saitoh, and Ryo Yoshinaka. 2017. The Time Complexity of the Token Swapping Problem and Its Parallel Variants. In WALCOM. Springer, Heidelberg, Germany, 448-459.Google Scholar
- Jens Koch, Terri M. Yu, Jay Gambetta, A. A. Houck, D. I. Schuster, J. Majer, Alexandre Blais, M. H. Devoret, S. M. Girvin, and R. J. Schoelkopf. 2007. Charge-insensitive qubit design derived from the Cooper pair box. Phys. Rev. A 76, 1 (2007), 04319.Google ScholarCross Ref
- Jonathan K. Lee, Jens Palsberg, and Fernando M. Q. Pereira. 2007. Aliased Register Allocation for Straight-Line Programs Is NP-Complete. In ICALP. Springer, Heidelberg, Germany, 258-273. Google ScholarDigital Library
- Daniel A Lidar and Todd A Brun. 2013. Quantum error correction. Cambridge University Press, Cambridge, UK.Google Scholar
- C. C. Lin, S. Sur-Kolay, and N. K. Jha. 2015. PAQCS: Physical Design-Aware Fault-Tolerant Quantum Circuit Synthesis. Transactions on Very Large Scale Integration (VLSI) Systems 23, 7 (2015), 1221-1234.Google ScholarDigital Library
- Chris Lomont. 2003. Quantum Circuit Identities. CoRR arXiv:quantph/0307111 (2003), 1-6.Google Scholar
- Dmitri Maslov. 2017. Basic circuit compilation techniques for an ion-trap quantum machine. New Journal of Physics 19, 2 (2017), 023035.Google ScholarCross Ref
- D. Maslov, S. M. Falconer, and M. Mosca. 2008. Quantum Circuit Placement. Transactions on Computer-Aided Design of Integrated Circuits and Systems 27, 4 (2008), 752-763. Google ScholarDigital Library
- M Mohseni, P Read, H Neven, S Boixo, V Denchev, R Babbush, A Fowler, V Smelyanskiy, and J Martinis. 2017. Commercialize early quantum technologies. Nature 543, 7644 (2017), 171.Google Scholar
- Michael A Nielsen and Isaac Chuang. 2000. Quantum computation and quantum information. Cambridge University Press, Cambridge, UK. Google ScholarDigital Library
- M. Pedram and A. Shafaei. 2016. Layout Optimization for Quantum Circuits with Linear Nearest Neighbor Architectures. Circuits and Systems Magazine 16, 2 (2016), 62-74.Google ScholarCross Ref
- Simon Perdrix. 2008. Quantum entanglement analysis based on abstract interpretation. In SAS. Springer, Heidelberg, Germany, 270-282. Google ScholarDigital Library
- Fernando Magno Quintao Pereira and Jens Palsberg. 2006. Register Allocation after Classic SSA elimination is NP-complete. In FOSSACS. Springer, Heidelberg, Germany, 79-93. Google ScholarDigital Library
- Jordi Petit. 2003. Experiments on the Minimum Linear Arrangement Problem. J. Exp. Algorithmics 8 (2003), 1-33. Google ScholarDigital Library
- Peter Selinger. 2004. A brief survey of quantum programming languages. In Functional and Logic Programming. Springer, Heidelberg, Germany, 61-69.Google Scholar
- A. Shafaei, M. Saeedi, and M. Pedram. 2014. Qubit placement to minimize communication overhead in 2D quantum architectures. In ASP-DAC. IEEE, Washington, DC, USA, 495-500.Google Scholar
- Peter W. Shor. 1997. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. Journal on Computing 26, 5 (1997), 1484-1509. Google ScholarDigital Library
- Robert S. Smith, Michael J. Curtis, and William J. Zeng. 2017. A Practical Quantum Instruction Set Architecture. arXiv arXiv:1608.03355 (2017), 1-15.Google Scholar
- Krysta M. Svore, Alfred V. Aho, Andrew W. Cross, Isaac Chuang, and Igor L. Markov. 2006. A Layered Software Architecture for Quantum Computing Design Tools. Computer 39, 1 (2006), 74-83. Google ScholarDigital Library
- Robert R Tucci. 1999. A Rudimentary Quantum Compiler (2nd Ed.). arXiv quant-ph/9902062 (1999), 1-25.Google Scholar
- Dave Wecker and Krysta M Svore. 2014. LIQUi|¿: A software design architecture and domain-specific language for quantum computing. arXiv quant-ph:1402.4467 (2014), 1-14.Google Scholar
- Laurence A. Wolsey. 2008. Mixed Integer Programming. Encyclopedia of Computer Science and Engineering Online, ecse244 (2008), -.Google Scholar
- Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno. 2014. Swapping Labeled Tokens on Graphs. Springer, Heidelberg, Germany, 364-375.Google Scholar
Index Terms
- Qubit allocation
Recommendations
An exact qubit allocation approach for NISQ architectures
AbstractThe noisy intermediate-scale quantum (NISQ) devices that have just emerged in recent years provide an opportunity for the physical realization of quantum circuits. As the first step of mapping quantum circuits to these devices, qubit allocation ...
Exact canonical decomposition of two-qubit operators in terms of CNOT
The canonical decomposition for two-qubit operators has proven very useful for applications in quantum computing. This decomposition generates equivalence classes up to local quantum gates. We provide a variety of complete, explicit decompositions of ...
A SWAP gate for qudits
We present a quantum SWAP gate valid for quantum systems of an arbitrary dimension. The gate generalizes the CNOT implementation of the SWAP gate for qubits and keeps its most important properties, like symmetry and simplicity. We only use three copies ...
Comments