Fixed-Depth Two-Qubit Circuits and the Monodromy Polytope

Eric C. Peterson; Gavin E. Crooks; Robert S. Smith

doi:10.22331/q-2020-03-26-247

Fixed-Depth Two-Qubit Circuits and the Monodromy Polytope

Eric C. Peterson, Gavin E. Crooks, and Robert S. Smith

Rigetti Quantum Computing, 2919 Seventh St, Berkeley, CA 94710

Published:	2020-03-26, volume 4, page 247
Eprint:	arXiv:1904.10541v3
Doi:	https://doi.org/10.22331/q-2020-03-26-247
Citation:	Quantum 4, 247 (2020).

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

Updated version: The authors have uploaded version v4 of this work to the arXiv which may contain updates or corrections not contained in the published version v3. The authors left the following comment on the arXiv:

Updated after initial publication to fix increasing/decreasing conventions and an incorrect Figure 6

Abstract

For a native gate set which includes all single-qubit gates, we apply results from symplectic geometry to analyze the spaces of two-qubit programs accessible within a fixed number of gates. These techniques yield an explicit description of this subspace as a convex polytope, presented by a family of linear inequalities themselves accessible via a finite calculation. We completely describe this family of inequalities in a variety of familiar example cases, and as a consequence we highlight a certain member of the ``$\mathrm{XY}$--family'' for which this subspace is particularly large, i.e., for which many two-qubit programs admit expression as low-depth circuits.

Featured image: Two-qubit programs which admit circuits using 3 (red), 4 (yellow), and 5 (blue) applications of √CZ.

► BibTeX data

@article{Peterson2020fixeddepthtwoqubit,
  doi = {10.22331/q-2020-03-26-247},
  url = {https://doi.org/10.22331/q-2020-03-26-247},
  title = {Fixed-{D}epth {T}wo-{Q}ubit {C}ircuits and the {M}onodromy {P}olytope},
  author = {Peterson, Eric C. and Crooks, Gavin E. and Smith, Robert S.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {4},
  pages = {247},
  month = mar,
  year = {2020}
}

► References

[1] S. Agnihotri and C. Woodward. Eigenvalues of products of unitary matrices and quantum Schubert calculus. Math. Res. Lett., 5(6):817–836, 1998. 10.4310/MRL.1998.v5.n6.a10.
https://doi.org/10.4310/MRL.1998.v5.n6.a10

[2] M. F. Atiyah. Convexity and commuting Hamiltonians. Bull. London Math. Soc., 14(1):1–15, 1982. 10.1112/blms/14.1.1.
https://doi.org/10.1112/blms/14.1.1

[3] M. F. Atiyah and R. Bott. The Yang-Mills equations over Riemann surfaces. Philos. Trans. Roy. Soc. London Ser. A, 308(1505):523–615, 1983. 10.1098/rsta.1983.0017.
https://doi.org/10.1098/rsta.1983.0017

[4] D. Avis. Living with lrs. In Discrete and computational geometry (Tokyo, 1998), volume 1763 of Lecture Notes in Comput. Sci., pages 47–56. Springer, Berlin, 2000. 10.1007/978-3-540-46515-7_4.
https://doi.org/10.1007/978-3-540-46515-7_4

[5] D. Avis and K. Fukuda. Reverse search for enumeration. volume 65, pages 21–46. 1996. 10.1016/0166-218X(95)00026-N. First International Colloquium on Graphs and Optimization (GOI), 1992 (Grimentz).
https://doi.org/10.1016/0166-218X(95)00026-N

[6] P. Belkale. Local systems on $\Bbb P^1-S$ for $S$ a finite set. Compositio Math., 129(1):67–86, 2001. 10.1023/A:1013195625868.
https://doi.org/10.1023/A:1013195625868

[7] A. Bertram, I. Ciocan-Fontanine, and W. Fulton. Quantum multiplication of Schur polynomials. J. Algebra, 219(2):728–746, 1999. 10.1006/jabr.1999.7960.
https://doi.org/10.1006/jabr.1999.7960

[8] A. Buch. Littlewood–Richardson calculator. http://sites.math.rutgers.edu/ asbuch/lrcalc/, 1999-2014.
http://sites.math.rutgers.edu/~asbuch/lrcalc/

[9] P. Bürgisser, C. Franks, A. Garg, R. M. de Oliveira, M. Walter, and A. Wigderson. Efficient algorithms for tensor scaling, quantum marginals, and moment polytopes. In M. Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 883–897. IEEE Computer Society, 2018. 10.1109/FOCS.2018.00088.
https://doi.org/10.1109/FOCS.2018.00088

[10] S. A. Caldwell, N. Didier, C. A. Ryan, E. A. Sete, A. Hudson, P. Karalekas, R. Manenti, M. P. da Silva, R. Sinclair, E. Acala, N. Alidoust, J. Angeles, A. Bestwick, M. Block, B. Bloom, A. Bradley, C. Bui, L. Capelluto, R. Chilcott, J. Cordova, G. Crossman, M. Curtis, S. Deshpande, T. E. Bouayadi, D. Girshovich, S. Hong, K. Kuang, M. Lenihan, T. Manning, A. Marchenkov, J. Marshall, R. Maydra, Y. Mohan, W. O'Brien, C. Osborn, J. Otterbach, A. Papageorge, J. P. Paquette, M. Pelstring, A. Polloreno, G. Prawiroatmodjo, V. Rawat, M. Reagor, R. Renzas, N. Rubin, D. Russell, M. Rust, D. Scarabelli, M. Scheer, M. Selvanayagam, R. Smith, A. Staley, M. Suska, N. Tezak, D. C. Thompson, T. W. To, M. Vahidpour, N. Vodrahalli, T. Whyland, K. Yadav, W. Zeng, and C. Rigetti. Parametrically Activated Entangling Gates Using Transmon Qubits. Physical Review Applied, 10:034050, Sep 2018, 1706.06562. 10.1103/PhysRevApplied.10.034050.
https://doi.org/10.1103/PhysRevApplied.10.034050
arXiv:1706.06562

[11] A. W. Cross, L. S. Bishop, S. Sheldon, P. D. Nation, and J. M. Gambetta. Validating quantum computers using randomized model circuits. Phys. Rev. A, 100:032328, Sep 2019. 10.1103/PhysRevA.100.032328.
https://doi.org/10.1103/PhysRevA.100.032328

[12] S. K. Donaldson. A new proof of a theorem of narasimhan and seshadri. J. Differential Geom., 18(2):269–277, 1983. 10.4310/jdg/1214437664.
https://doi.org/10.4310/jdg/1214437664

[13] S. K. Donaldson. Boundary value problems for Yang-Mills fields. J. Geom. Phys., 8(1-4):89–122, 1992. 10.1016/0393-0440(92)90044-2.
https://doi.org/10.1016/0393-0440(92)90044-2

[14] A. Edelman, T. A. Arias, and S. T. Smith. The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl., 20(2):303–353, 1999. 10.1137/S0895479895290954.
https://doi.org/10.1137/S0895479895290954

[15] L. Euler. Novi commentarii Academiae Scientiarum Imperialis Petropolitanae, volume t.20. Petropolis, Typis Academiae Scientarum, 1775.

[16] E. Falbel and R. A. Wentworth. Eigenvalues of products of unitary matrices and Lagrangian involutions. Topology, 45(1):65–99, 2006. 10.1016/j.top.2005.06.003.
https://doi.org/10.1016/j.top.2005.06.003

[17] C. Franks. Operator scaling with specified marginals. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 190–203, New York, NY, USA, 2018. Association for Computing Machinery. 10.1145/3188745.3188932.
https://doi.org/10.1145/3188745.3188932

[18] W. Fulton and R. Pandharipande. Notes on stable maps and quantum cohomology. In Algebraic geometry—Santa Cruz 1995, volume 62 of Proc. Sympos. Pure Math., pages 45–96. Amer. Math. Soc., Providence, RI, 1997. 10.1090/pspum/062.2/1492534.
https://doi.org/10.1090/pspum/062.2/1492534

[19] A. N. Glaudell, N. J. Ross, and J. M. Taylor. Optimal Two-Qubit Circuits for Universal Fault-Tolerant Quantum Computation. arXiv e-prints, page arXiv:2001.05997, Jan. 2020, 2001.05997.
arXiv:2001.05997

[20] V. Guillemin and S. Sternberg. Convexity properties of the moment mapping. Invent. Math., 67(3):491–513, 1982. 10.1007/BF01398933.
https://doi.org/10.1007/BF01398933

[21] V. Guillemin and S. Sternberg. Convexity properties of the moment mapping. II. Invent. Math., 77(3):533–546, 1984. 10.1007/BF01388837.
https://doi.org/10.1007/BF01388837

[22] B. Hall. Lie groups, Lie algebras, and representations, volume 222 of Graduate Texts in Mathematics. Springer, Cham, second edition, 2015. 10.1007/978-3-319-13467-3. An elementary introduction.
https://doi.org/10.1007/978-3-319-13467-3

[23] R. Hartshorne. Algebraic geometry. Springer-Verlag, New York-Heidelberg, 1977. https://doi.org/10.1007/978-1-4757-3849-0. Graduate Texts in Mathematics, No. 52.
https://doi.org/10.1007/978-1-4757-3849-0

[24] A. Horn. Eigenvalues of sums of Hermitian matrices. Pacific J. Math., 12:225–241, 1962. URL http://projecteuclid.org/euclid.pjm/1103036720.
http://projecteuclid.org/euclid.pjm/1103036720

[25] J. E. Humphreys. Reflection groups and Coxeter groups, volume 29 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1990. 10.1017/CBO9780511623646.
https://doi.org/10.1017/CBO9780511623646

[26] L. C. Jeffrey and J. Weitsman. Bohr-Sommerfeld orbits in the moduli space of flat connections and the Verlinde dimension formula. Communications in Mathematical Physics, 150(3):593–630, Dec. 1992. 10.1007/BF02096964.
https://doi.org/10.1007/BF02096964

[27] F. Kirwan. Convexity properties of the moment mapping. III. Invent. Math., 77(3):547–552, 1984. 10.1007/BF01388838.
https://doi.org/10.1007/BF01388838

[28] A. A. Klyachko. Stable bundles, representation theory and Hermitian operators. Selecta Math. (N.S.), 4(3):419–445, 1998. 10.1007/s000290050037.
https://doi.org/10.1007/s000290050037

[29] A. Knutson. The symplectic and algebraic geometry of horn's problem. Linear Algebra and its Applications, 319(1):61 – 81, 2000. https://doi.org/10.1016/S0024-3795(00)00220-2.
https://doi.org/10.1016/S0024-3795(00)00220-2

[30] M. Kontsevich and Y. Manin. Gromov-Witten classes, quantum cohomology, and enumerative geometry. Comm. Math. Phys., 164(3):525–562, 1994. URL http://projecteuclid.org/euclid.cmp/1104270948.
http://projecteuclid.org/euclid.cmp/1104270948

[31] B. Kraus and J. I. Cirac. Optimal creation of entanglement using a two-qubit gate. Physical Review A, 63:062309, Jun 2001, quant-ph/0011050. 10.1103/PhysRevA.63.062309.
https://doi.org/10.1103/PhysRevA.63.062309
arXiv:quant-ph/0011050

[32] J. Lawrence. Polytope volume computation. Math. Comp., 57(195):259–271, 1991. 10.2307/2938672.
https://doi.org/10.2307/2938672

[33] Y. Makhlin. Nonlocal properties of two-qubit gates and mixed states, and the optimization of quantum computations. Quantum Information Processing, 1(4):243–252, Aug. 2002. 10.1023/A:1022144002391.
https://doi.org/10.1023/A:1022144002391

[34] V. B. Mehta and C. S. Seshadri. Moduli of vector bundles on curves with parabolic structures. Math. Ann., 248(3):205–239, 1980. 10.1007/BF01420526.
https://doi.org/10.1007/BF01420526

[35] E. Meinrenken and C. Woodward. A symplectic proof of Verlinde factorization. eprint arXiv:dg-ga/961201, Dec. 1996, dg-ga/9612018.
arXiv:dg-ga/9612018

[36] E. Meinrenken and C. Woodward. Hamiltonian loop group actions and verlinde factorization. J. Differential Geom., 50(3):417–469, 1998. 10.4310/jdg/1214424966.
https://doi.org/10.4310/jdg/1214424966

[37] M. S. Narasimhan and C. S. Seshadri. Stable and unitary vector bundles on a compact Riemann surface. Ann. of Math. (2), 82:540–567, 1965. 10.2307/1970710.
https://doi.org/10.2307/1970710

[38] M. A. Nielsen. A simple formula for the average gate fidelity of a quantum dynamical operation. Physics Letters A, 303(4):249 – 252, 2002. https://doi.org/10.1016/S0375-9601(02)01272-0.
https://doi.org/10.1016/S0375-9601(02)01272-0

[39] L. H. Pedersen, N. M. Møller, and K. Mølmer. Fidelity of quantum operations. Phys. Lett. A, 367:47–51, July 2007, quant-ph/0701138. 10.1016/j.physleta.2007.02.069.
https://doi.org/10.1016/j.physleta.2007.02.069
arXiv:quant-ph/0701138

[40] J. Råde. On the Yang-Mills heat equation in two and three dimensions. J. Reine Angew. Math., 431:123–163, 1992. 10.1515/crll.1992.431.123.
https://doi.org/10.1515/crll.1992.431.123

[41] A. Sard. The measure of the critical values of differentiable maps. Bull. Amer. Math. Soc., 48:883–890, 1942. 10.1090/S0002-9904-1942-07811-6.
https://doi.org/10.1090/S0002-9904-1942-07811-6

[42] N. Schuch and J. Siewert. Natural two-qubit gate for quantum computation using the XY interaction. Physical Review A, 67:032301, Mar 2003, quant-ph/0209035. 10.1103/PhysRevA.67.032301.
https://doi.org/10.1103/PhysRevA.67.032301
arXiv:quant-ph/0209035

[43] V. V. Shende, S. S. Bullock, and I. L. Markov. Recognizing small-circuit structure in two-qubit operators. Physical Review A, 70:012310, July 2004, quant-ph/0308045. 10.1103/PhysRevA.70.012310.
https://doi.org/10.1103/PhysRevA.70.012310
arXiv:quant-ph/0308045

[44] V. V. Shende, S. S. Bullock, and I. L. Markov. Synthesis of quantum-logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(6):1000–1010, 2006. 10.1109/TCAD.2005.855930.
https://doi.org/10.1109/TCAD.2005.855930

[45] V. V. Shende, I. L. Markov, and S. S. Bullock. Minimal universal two-qubit controlled-NOT-based circuits. Phys. Rev. A, 69:062321, 2004. 10.1103/PhysRevA.69.062321.
https://doi.org/10.1103/PhysRevA.69.062321

[46] R. S. Smith, M. J. Curtis, and W. J. Zeng. A Practical Quantum Instruction Set Architecture. arXiv e-prints, page arXiv:1608.03355, Aug. 2016, 1608.03355.
arXiv:1608.03355

[47] P. Watts, J. Vala, M. M. Müller, T. Calarco, K. B. Whaley, D. M. Reich, M. H. Goerz, and C. P. Koch. Optimizing for an arbitrary perfect entangler. i. functionals. Phys. Rev. A, 91:062306, Jun 2015. 10.1103/PhysRevA.91.062306.
https://doi.org/10.1103/PhysRevA.91.062306

[48] H.-R. Wei and Y.-M. Di. Decomposition of orthogonal matrix and synthesis of two-qubit and three-qubit orthogonal gates. Quantum Info. Comput., 12(3–4):262–270, Mar. 2012.

[49] J. Zhang, J. Vala, S. Sastry, and K. B. Whaley. Geometric theory of nonlocal two-qubit operations. Phys. Rev. A, 67:042313, 2003. 10.1103/PhysRevA.67.042313.
https://doi.org/10.1103/PhysRevA.67.042313

[50] J. Zhang, J. Vala, S. Sastry, and K. B. Whaley. Minimum Construction of Two-Qubit Quantum Operations. Phys. Rev. Lett. , 93:020502, Jul 2004, quant-ph/0312193. 10.1103/PhysRevLett.93.020502.
https://doi.org/10.1103/PhysRevLett.93.020502
arXiv:quant-ph/0312193

Cited by

[1] Lingling Lao, Alexander Korotkov, Zhang Jiang, Wojciech Mruczkiewicz, Thomas E O'Brien, and Dan E Browne, "Software mitigation of coherent two-qubit gate errors", Quantum Science and Technology 7 2, 025021 (2022).

[2] Bochen Tan and Jason Cong, Design Automation of Quantum Computers 25 (2023) ISBN:978-3-031-15698-4.

[3] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik, "Noisy intermediate-scale quantum algorithms", Reviews of Modern Physics 94 1, 015004 (2022).

[4] Evan McKinney, Mingkang Xia, Chao Zhou, Pinlei Lu, Michael Hatridge, and Alex K. Jones, 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA) 759 (2023) ISBN:978-1-6654-7652-2.

[5] Lingling Lao, Prakash Murali, Margaret Martonosi, and Dan Browne, 2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA) 846 (2021) ISBN:978-1-6654-3333-4.

[6] Deanna M. Abrams, Nicolas Didier, Blake R. Johnson, Marcus P. da Silva, and Colm A. Ryan, "Implementation of XY entangling gates with a single calibrated pulse", Nature Electronics 3 12, 744 (2020).

[7] Cupjin Huang, Tenghui Wang, Feng Wu, Dawei Ding, Qi Ye, Linghang Kong, Fang Zhang, Xiaotong Ni, Zhijun Song, Yaoyun Shi, Hui-Hai Zhao, Chunqing Deng, and Jianxin Chen, "Quantum Instruction Set Design for Performance", Physical Review Letters 130 7, 070601 (2023).

[8] David Rodríguez Pérez, Paul Varosy, Ziqian Li, Tanay Roy, Eliot Kapit, and David Schuster, "Error-Divisible Two-Qubit Gates", Physical Review Applied 19 2, 024043 (2023).

[9] Kentaro Kubo and Hayato Goto, "Fast parametric two-qubit gate for highly detuned fixed-frequency superconducting qubits using a double-transmon coupler", Applied Physics Letters 122 6, 064001 (2023).

[10] Liam Madden and Andrea Simonetto, "Best Approximate Quantum Compiling Problems", ACM Transactions on Quantum Computing 3 2, 1 (2022).

[11] Eric C. Peterson, Lev S. Bishop, and Ali Javadi-Abhari, "Optimal synthesis into fixed XX interactions", Quantum 6, 696 (2022).

[12] Wonho Jang, Koji Terashi, Masahiko Saito, Christian W. Bauer, Benjamin Nachman, Yutaro Iiyama, Ryunosuke Okubo, and Ryu Sawada, "Initial-State Dependent Optimization of Controlled Gate Operations with Quantum Computer", Quantum 6, 798 (2022).

[13] Gavin E. Crooks, "Gradients of parameterized quantum gates using the parameter-shift rule and gate decomposition", arXiv:1905.13311, (2019).

[14] Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan, "t|ket⟩: a retargetable compiler for NISQ devices", Quantum Science and Technology 6 1, 014003 (2021).

[15] Peter J. Karalekas, Nikolas A. Tezak, Eric C. Peterson, Colm A. Ryan, Marcus P. da Silva, and Robert S. Smith, "A quantum-classical cloud platform optimized for variational hybrid algorithms", Quantum Science and Technology 5 2, 024003 (2020).

[16] A. D. Corcoles, A. Kandala, A. Javadi-Abhari, D. T. McClure, A. W. Cross, K. Temme, P. D. Nation, M. Steffen, and J. M. Gambetta, "Challenges and Opportunities of Near-Term Quantum Computing Systems", arXiv:1910.02894, (2019).

[17] Deanna M. Abrams, Nicolas Didier, Blake R. Johnson, Marcus P. da Silva, and Colm A. Ryan, "Implementation of the XY interaction family with calibration of a single pulse", arXiv:1912.04424, (2019).

[18] R. S. Smith, E. C. Peterson, M. G. Skilbeck, and E. J. Davis, "An open-source, industrial-strength optimizing compiler for quantum programs", Quantum Science and Technology 5 4, 044001 (2020).

[19] M. Sohaib Alam, Noah F. Berthusen, and Peter P. Orth, "Quantum Logic Gate Synthesis as a Markov Decision Process", arXiv:1912.12002, (2019).

The above citations are from Crossref's cited-by service (last updated successfully 2023-03-31 07:01:11) and SAO/NASA ADS (last updated successfully 2023-03-31 07:01:12). 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.