Compiling Quantum Circuits for Dynamically Field-Programmable Neutral Atoms Array Processors

Daniel Bochen Tan1, Dolev Bluvstein2, Mikhail D. Lukin2, and Jason Cong1

1Computer Science Department, University of California, Los Angeles, CA 90095
2Department of Physics, Harvard University, Cambridge, MA 02138

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


Dynamically field-programmable qubit arrays (DPQA) have recently emerged as a promising platform for quantum information processing. In DPQA, atomic qubits are selectively loaded into arrays of optical traps that can be reconfigured during the computation itself. Leveraging qubit transport and parallel, entangling quantum operations, different pairs of qubits, even those initially far away, can be entangled at different stages of the quantum program execution. Such reconfigurability and non-local connectivity present new challenges for compilation, especially in the layout synthesis step which places and routes the qubits and schedules the gates. In this paper, we consider a DPQA architecture that contains multiple arrays and supports 2D array movements, representing cutting-edge experimental platforms. Within this architecture, we discretize the state space and formulate layout synthesis as a satisfiability modulo theories problem, which can be solved by existing solvers optimally in terms of circuit depth. For a set of benchmark circuits generated by random graphs with complex connectivities, our compiler OLSQ-DPQA reduces the number of two-qubit entangling gates on small problem instances by 1.7x compared to optimal compilation results on a fixed planar architecture. To further improve scalability and practicality of the method, we introduce a greedy heuristic inspired by the iterative peeling approach in classical integrated circuit routing. Using a hybrid approach that combined the greedy and optimal methods, we demonstrate that our DPQA-based compiled circuits feature reduced scaling overhead compared to a grid fixed architecture, resulting in 5.1X less two-qubit gates for 90 qubit quantum circuits. These methods enable programmable, complex quantum circuits with neutral atom quantum computers, as well as informing both future compilers and future hardware choices.

Neutral atom arrays are gaining popularity as a platform for quantum computing because of the large number of qubits, high-fidelity operations, and long coherence. A unique feature of these arrays is the ability to change the coupling between qubits by physically moving them around. To run quantum circuits to this reconfigurable architecture, our compiler places qubits to specific positions and routes their movements through various stages of operation. In this paper, we systematically present the design space and constraints in such compilation. We also provide an open-source compiler that not only tackles these challenges but can generate animations of how qubits move.

► BibTeX data

► References

[1] B. Tan, D. Bluvstein, M. D. Lukin, and J. Cong. ``Qubit mapping for reconfigurable atom arrays''. In Proceedings of the 41th IEEE/​ACM International Conference on Computer-Aided Design (ICCAD). San Diego, California (2022). Association for Computing Machinery.

[2] J. Beugnon, C. Tuchendler, H. Marion, A. Gaëtan, Y. Miroshnychenko, Y. R. P. Sortais, A. M. Lance, M. P. A. Jones, G. Messin, A. Browaeys, and P. Grangier. ``Two-dimensional transport and transfer of a single atomic qubit in optical tweezers''. Nature Physics 3, 696–699 (2007).

[3] D. Bluvstein, H. Levine, G. Semeghini, T. T. Wang, S. Ebadi, M. Kalinowski, A. Keesling, N. Maskara, H. Pichler, M. Greiner, V. Vuletić, and M. D. Lukin. ``A quantum processor based on coherent transport of entangled atom arrays''. Nature 604, 451–456 (2022).

[4] S. J. Evered, D. Bluvstein, M. Kalinowski, S. Ebadi, T. Manovitz, H. Zhou, S. H. Li, A. A. Geim, T. T. Wang, N. Maskara, H. Levine, G. Semeghini, M. Greiner, V. Vuletić, and M. D. Lukin. ``High-fidelity parallel entangling gates on a neutral-atom quantum computer''. Nature 622, 268–272 (2023).

[5] Google Quantum AI. ``Quantum computer datasheet''. url: https:/​/​​hardware/​datasheet/​weber.pdf.

[6] IBM. ``IBM quantum processor''. url: https:/​/​​services/​docs/​services/​manage/​systems/​processors.

[7] Rigetti. ``Scalable quantum systems built from the chip up to power practical applications''. url: https:/​/​​what-we-build.

[8] C. Chamberland, G. Zhu, T. J. Yoder, J. B. Hertzberg, and A. W. Cross. ``Topological and subsystem codes on low-degree graphs with flag qubits''. Physical Review X 10, 011022 (2020).

[9] Quantinuum. ``Quantinuum H1, powered by Honeywell''. url: https:/​/​​products/​h1.

[10] IonQ. ``IonQ technology''. url: https:/​/​​teczhnology.

[11] D. Kielpinski, C. Monroe, and D. J. Wineland. ``Architecture for a large-scale ion-trap quantum computer''. Nature 417, 709–711 (2002).

[12] J. M. Pino, J. M. Dreiling, C. Figgatt, J. P. Gaebler, S. A. Moses, M. Allman, C. Baldwin, M. Foss-Feig, D. Hayes, K. Mayer, et al. ``Demonstration of the trapped-ion quantum CCD computer architecture''. Nature 592, 209–213 (2021).

[13] S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H. Pichler, S.-T. Wang, M. Greiner, V. Vuletic, and M. D. Lukin. ``Quantum optimization of maximum independent set using Rydberg atom arrays''. Science 376, 1209–1215 (2022).

[14] W.-H. Lin, J. Kimko, B. Tan, N. Bjørner, and J. Cong. ``Scalable optimal layout synthesis for NISQ quantum processors''. In 2023 60th ACM/​IEEE Design Automation Conference (DAC). (2023).

[15] B. Tan and J. Cong. ``Optimality study of existing quantum computing layout synthesis tools''. IEEE Transactions on Computers 70, 1363–1373 (2021).

[16] B. Tan and J. Cong. ``Optimal layout synthesis for quantum computing''. In Proceedings of the 39th IEEE/​ACM International Conference on Computer-Aided Design (ICCAD). Virtual Event, USA (2020). Association for Computing Machinery.

[17] G. Li, Y. Ding, and Y. Xie. ``Tackling the qubit mapping problem for NISQ-era quantum devices''. In Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). Providence, RI, USA (2019). ACM Press.

[18] A. Zulehner and R. Wille. ``Compiling SU(4) quantum circuits to IBM QX architectures''. In Proceedings of the 24th Asia and South Pacific Design Automation Conference (ASP-DAC). Tokyo, Japan (2019). ACM Press.

[19] R. Wille, L. Burgholzer, and A. Zulehner. ``Mapping quantum circuits to IBM QX architectures using the minimal number of SWAP and H operations''. In Proceedings of the 56th Annual Design Automation Conference 2019 (DAC). Las Vegas, NV, USA (2019). ACM Press.

[20] D. Bhattacharjee, A. A. Saki, M. Alam, A. Chattopadhyay, and S. Ghosh. ``MUQUT: Multi-constraint quantum circuit mapping on NISQ computers: Invited paper''. In Proceedings of the 38th IEEE/​ACM International Conference on Computer-Aided Design (ICCAD). Westminster, CO, USA (2019). IEEE.

[21] P. Murali, N. M. Linke, M. Martonosi, A. J. Abhari, N. H. Nguyen, and C. H. Alderete. ``Full-stack, real-system quantum computer studies: Architectural comparisons and design insights''. In Proceedings of the 46th International Symposium on Computer Architecture (ISCA). Phoenix, Arizona (2019). ACM Press.

[22] C. Zhang, A. B. Hayes, L. Qiu, Y. Jin, Y. Chen, and E. Z. Zhang. ``Time-optimal qubit mapping''. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS). Virtual USA (2021). ACM.

[23] B. Tan and J. Cong. ``Optimal qubit mapping with simultaneous gate absorption''. In Proceedings of the 40th IEEE/​ACM International Conference on Computer-Aided Design (ICCAD). Munich, Germany (2021). Association for Computing Machinery.

[24] D. Maslov, S. M. Falconer, and M. Mosca. ``Quantum circuit placement''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27, 752–763 (2008).

[25] A. Shafaei, M. Saeedi, and M. Pedram. ``Qubit placement to minimize communication overhead in 2D quantum architectures''. In Proceedings of the 19th Asia and South Pacific Design Automation Conference (ASP-DAC). Singapore (2014). IEEE.

[26] D. Bhattacharjee and A. Chattopadhyay. ``Depth-optimal quantum circuit placement for arbitrary topologies'' (2017). arXiv:1703.08540.

[27] M. Y. Siraichi, V. F. dos Santos, S. Collange, and F. M. Q. Pereira. ``Qubit allocation''. In Proceedings of the 16th International Symposium on Code Generation and Optimization (CGO). Vienna, Austria (2018). ACM Press.

[28] A. Ash-Saki, M. Alam, and S. Ghosh. ``QURE: Qubit re-allocation in noisy intermediate-scale quantum computers''. In Proceedings of the 56th Annual Design Automation Conference (DAC). Las Vegas, NV, USA (2019). ACM Press.

[29] M. Alam, A. Ash-Saki, and S. Ghosh. ``An efficient circuit compilation flow for quantum approximate optimization algorithm''. In Proceedings of the 57th ACM/​IEEE Design Automation Conference (DAC). San Francisco, CA, USA (2020). IEEE.

[30] A. Botea, A. Kishimoto, and R. Marinescu. ``On the complexity of quantum circuit compilation''. In Proceedings of the 11th Annual Symposium on Combinatorial Search. Stockholm, Sweden (2018). AAAI Press.

[31] T. Patel, D. Silver, and D. Tiwari. ``Geyser: A compilation framework for quantum computing with neutral atoms''. In Proceedings of the 49th Annual International Symposium on Computer Architecture (ISCA). New York, NY, USA (2022). Association for Computing Machinery.

[32] J. M. Baker, A. Litteken, C. Duckering, et al. ``Exploiting long-distance interactions and tolerating atom loss in neutral atom quantum architectures''. In Proceedings of the 48th Annual International Symposium on Computer Architecture (ISCA). Virtual Event (2021). IEEE Press.

[33] S. Brandhofer, H. P. Büchler, and I. Polian. ``Optimal mapping for near-term quantum architectures based on Rydberg atoms''. In Proceedings of the 40th IEEE/​ACM International Conference on Computer-Aided Design (ICCAD). Munich, Germany (2021). Association for Computing Machinery.

[34] A. Browaeys, D. Barredo, and T. Lahaye. ``Experimental investigations of dipole–dipole interactions between a few Rydberg atoms''. Journal of Physics B: Atomic, Molecular and Optical Physics 49, 152001 (2016).

[35] D. Barredo, S. de Léséleuc, V. Lienhard, T. Lahaye, and A. Browaeys. ``An atom-by-atom assembler of defect-free arbitrary two-dimensional atomic arrays''. Science 354, 1021–1023 (2016).

[36] H. Labuhn, D. Barredo, S. Ravets, S. de Léséleuc, T. Macrì, T. Lahaye, and A. Browaeys. ``Tunable two-dimensional arrays of single Rydberg atoms for realizing quantum Ising models''. Nature 534, 667–670 (2016).

[37] P. Scholl, M. Schuler, H. J. Williams, A. A. Eberharter, D. Barredo, K.-N. Schymik, V. Lienhard, L.-P. Henry, T. C. Lang, T. Lahaye, A. M. Läuchli, and A. Browaeys. ``Quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms''. Nature 595, 233 – 238 (2021).

[38] S. Ebadi, T. T. Wang, H. Levine, A. Keesling, G. Semeghini, A. Omran, D. Bluvstein, R. Samajdar, H. Pichler, W. W. Ho, S. Choi, S. Sachdev, M. Greiner, V. Vuletić, and M. D. Lukin. ``Quantum phases of matter on a 256-atom programmable quantum simulator''. Nature 595, 227–232 (2021).

[39] E. Urban, T. A. Johnson, T. Henage, L. Isenhower, D. D. Yavuz, T. G. Walker, and M. Saffman. ``Observation of Rydberg blockade between two atoms''. Nature Physics 5, 110–114 (2008).

[40] H. Levine, A. Keesling, G. Semeghini, A. Omran, T. T. Wang, S. Ebadi, H. Bernien, M. Greiner, V. Vuletić, H. Pichler, and M. D. Lukin. ``Parallel implementation of high-fidelity multi-qubit gates with neutral atoms''. Physical Review Letters 123, 170503 (2019).

[41] P. Gokhale, A. Javadi-Abhari, N. Earnest, Y. Shi, and F. T. Chong. ``Optimized quantum compilation for near-term algorithms with OpenPulse''. In Proceedings of the 53rd Annual IEEE/​ACM International Symposium on Microarchitecture (MICRO). Athens, Greece (2020). IEEE.

[42] S. Sivarajah, S. Dilkes, A. Cowtan, W. Simmons, A. Edgington, and R. Duncan. ``t$|$ket$\rangle$: A retargetable compiler for NISQ devices''. Quantum Science and Technology 6, 014003 (2020).

[43] M. P. Harrigan, K. J. Sung, M. Neeley, K. J. Satzinger, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, R. Barends, S. Boixo, M. Broughton, B. B. Buckley, D. A. Buell, B. Burkett, N. Bushnell, Y. Chen, Z. Chen, Ben Chiaro, R. Collins, W. Courtney, S. Demura, A. Dunsworth, D. Eppens, A. Fowler, B. Foxen, C. Gidney, M. Giustina, R. Graff, S. Habegger, A. Ho, S. Hong, T. Huang, L. B. Ioffe, S. V. Isakov, E. Jeffrey, Z. Jiang, C. Jones, D. Kafri, K. Kechedzhi, J. Kelly, S. Kim, P. V. Klimov, A. N. Korotkov, F. Kostritsa, D. Landhuis, P. Laptev, M. Lindmark, M. Leib, O. Martin, J. M. Martinis, J. R. McClean, M. McEwen, A. Megrant, X. Mi, M. Mohseni, W. Mruczkiewicz, J. Mutus, O. Naaman, C. Neill, F. Neukart, M. Y. Niu, T. E. O’Brien, B. O’Gorman, E. Ostby, A. Petukhov, H. Putterman, C. Quintana, P. Roushan, N. C. Rubin, D. Sank, A. Skolik, V. Smelyanskiy, D. Strain, M. Streif, M. Szalay, A. Vainsencher, T. White, Z. J. Yao, P. Yeh, A. Zalcman, L. Zhou, H. Neven, D. Bacon, E. Lucero, E. Farhi, and R. Babbush. ``Quantum approximate optimization of non-planar graph problems on a planar superconducting processor''. Nature Physics 17, 332–336 (2021).

[44] Qiskit contributors. ``Qiskit: An open-source framework for quantum computing'' (2023).

[45] J. Cong, M. Hossain, and N. Sherwani. ``A provably good multilayer topological planar routing algorithm in IC layout designs''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 12, 70–78 (1993).

[46] L. de Moura and N. Bjørner. ``Z3: An efficient SMT solver''. In C. R. Ramakrishnan and J. Rehof, editors, Tools and Algorithms for the Construction and Analysis of Systems. Berlin, Heidelberg (2008). Springer.

[47] A. Ignatiev, A. Morgado, and J. Marques-Silva. ``PySAT: A Python toolkit for prototyping with SAT oracles''. In SAT. (2018).

[48] A. Hagberg, P. Swart, and D. S Chult. ``Exploring network structure, dynamics, and function using NetworkX''. Technical report. Los Alamos National Lab.(LANL), Los Alamos, NM (United States) (2008).

[49] J. D. Hunter. ``Matplotlib: A 2D graphics environment''. Computing in Science & Engineering 9, 90–95 (2007).

[50] T. M. Graham, Y. Song, J. Scott, C. Poole, L. Phuttitarn, K. Jooya, P. Eichler, X. Jiang, A. Marra, B. Grinkemeyer, M. Kwon, M. Ebert, J. Cherek, M. T. Lichtman, M. Gillette, J. Gilbert, D. Bowman, T. Ballance, C. Campbell, E. D. Dahl, O. Crawford, N. S. Blunt, B. Rogers, T. Noel, and M. Saffman. ``Multi-qubit entanglement and algorithms on a neutral-atom quantum computer''. Nature 604, 457–462 (2022).

[51] Y. S. Weinstein, M. Pravia, E. Fortunato, S. Lloyd, and D. G. Cory. ``Implementation of the quantum fourier transform''. Physical review letters 86, 1889 (2001).

[52] S. Debnath, N. M. Linke, C. Figgatt, K. A. Landsman, K. Wright, and C. Monroe. ``Demonstration of a small programmable quantum computer with atomic qubits''. Nature 536, 63–66 (2016).

[53] A. Grospellier, L. Grouès, A. Krishna, and A. Leverrier. ``Combining hard and soft decoders for hypergraph product codes''. Quantum 5, 432 (2021).

[54] M. Kalinowski, N. Maskara, and M. D. Lukin. ``Non-abelian floquet spin liquids in a digital Rydberg simulator'' (2023). arXiv:2211.00017.

[55] E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. ``Quantum computation by adiabatic evolution'' (2000). arXiv:quant-ph/​0001106.

[56] F. Arute, K. Arya, R. Babbush, et al. ``Quantum supremacy using a programmable superconducting processor''. Nature 574, 505–510 (2019).

[57] H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu, P. Hu, X.-Y. Yang, W.-J. Zhang, H. Li, Y. Li, X. Jiang, L. Gan, G. Yang, L. You, Z. Wang, L. Li, N.-L. Liu, C.-Y. Lu, and J.-W. Pan. ``Quantum computational advantage using photons''. Science 370, 1460–1463 (2020).

[58] D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kalinowski, D. Hangleiter, et al. ``Logical quantum processor based on reconfigurable atom arrays''. Nature 626, 58–65 (2024).

[59] K. Singh, S. Anand, A. Pocklington, J. T. Kemp, and H. Bernien. ``Dual-element, two-dimensional atom array with continuous-mode operation''. Physical Review X 12, 011040 (2022).

[60] E. Farhi, J. Goldstone, and S. Gutmann. ``A quantum approximate optimization algorithm'' (2014). arXiv:1411.4028.

[61] H. Silvério, S. Grijalva, C. Dalyac, L. Leclerc, P. J. Karalekas, N. Shammah, M. Beji, L.-P. Henry, and L. Henriet. ``Pulser: An open-source package for the design of pulse sequences in programmable neutral-atom arrays''. Quantum 6, 629 (2022).

[62] H. Pichler, S.-T. Wang, L. Zhou, S. Choi, and M. D. Lukin. ``Quantum optimization for maximum independent set using Rydberg atom arrays'' (2018). arXiv:1808.10816.

[63] C. Mead and L. Conway. ``Introduction to VLSI systems''. Addison-Wesley. USA (1980). url: https:/​/​​people/​conway/​VLSI/​VLSIText/​PP-V2/​V2.pdf.

[64] A. Li, S. Stein, S. Krishnamoorthy, and J. Ang. ``QASMBench: A low-level quantum benchmark suite for NISQ evaluation and simulation''. ACM Transactions on Quantum Computing (2022).

Cited by

[1] Ludwig Schmid, David F Locher, Manuel Rispler, Sebastian Blatt, Johannes Zeiher, Markus Müller, and Robert Wille, "Computational capabilities and compiler development for neutral atom quantum processors—connecting tool developers and hardware experts", Quantum Science and Technology 9 3, 033001 (2024).

[2] Dolev Bluvstein, Simon J. Evered, Alexandra A. Geim, Sophie H. Li, Hengyun Zhou, Tom Manovitz, Sepehr Ebadi, Madelyn Cain, Marcin Kalinowski, Dominik Hangleiter, J. Pablo Bonilla Ataides, Nishad Maskara, Iris Cong, Xun Gao, Pedro Sales Rodriguez, Thomas Karolyshyn, Giulia Semeghini, Michael J. Gullans, Markus Greiner, Vladan Vuletić, and Mikhail D. Lukin, "Logical quantum processor based on reconfigurable atom arrays", Nature 626 7997, 58 (2024).

[3] Daniel Bochen Tan, Shuohao Ping, and Jason Cong, "Depth-Optimal Addressing of 2D Qubit Array with 1D Controls Based on Exact Binary Matrix Factorization", arXiv:2401.13807, (2024).

[4] Korbinian Staudacher, Ludwig Schmid, Johannes Zeiher, Robert Wille, and Dieter Kranzlmüller, "Multi-controlled Phase Gate Synthesis with ZX-calculus applied to Neutral Atom Hardware", arXiv:2403.10864, (2024).

[5] Hanrui Wang, Bochen Tan, Pengyu Liu, Yilian Liu, Jiaqi Gu, Jason Cong, and Song Han, "Q-Pilot: Field Programmable Quantum Array Compilation with Flying Ancillas", arXiv:2311.16190, (2023).

[6] Joshua Viszlai, Willers Yang, Sophia Fuhui Lin, Junyu Liu, Natalia Nottingham, Jonathan M. Baker, and Frederic T. Chong, "Matching Generalized-Bicycle Codes to Neutral Atoms for Low-Overhead Fault-Tolerance", arXiv:2311.16980, (2023).

[7] Ludwig Schmid, Sunghye Park, Seokhyeong Kang, and Robert Wille, "Hybrid Circuit Mapping: Leveraging the Full Spectrum of Computational Capabilities of Neutral Atom Quantum Computers", arXiv:2311.14164, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-04-12 02:21:56) and SAO/NASA ADS (last updated successfully 2024-04-12 02:21:57). The list may be incomplete as not all publishers provide suitable and complete citation data.