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

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


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.

► BibTeX data

► 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.

[2] M. F. Atiyah. Convexity and commuting Hamiltonians. Bull. London Math. Soc., 14(1):1–15, 1982. 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.

[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.

[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).

[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.

[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.

[8] A. Buch. Littlewood–Richardson calculator. http:/​/​​ asbuch/​lrcalc/​, 1999-2014.

[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.

[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.

[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.

[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.

[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.

[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.

[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/​

[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.

[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.

[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.

[20] V. Guillemin and S. Sternberg. Convexity properties of the moment mapping. Invent. Math., 67(3):491–513, 1982. 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.

[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.

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

[24] A. Horn. Eigenvalues of sums of Hermitian matrices. Pacific J. Math., 12:225–241, 1962. URL http:/​/​​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.

[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.

[27] F. Kirwan. Convexity properties of the moment mapping. III. Invent. Math., 77(3):547–552, 1984. 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.

[29] A. Knutson. The symplectic and algebraic geometry of horn's problem. Linear Algebra and its Applications, 319(1):61 – 81, 2000. https:/​/​​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:/​/​​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.

[32] J. Lawrence. Polytope volume computation. Math. Comp., 57(195):259–271, 1991. 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.

[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.

[35] E. Meinrenken and C. Woodward. A symplectic proof of Verlinde factorization. eprint arXiv:dg-ga/​961201, Dec. 1996, 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.

[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.

[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:/​/​​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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

[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.

Cited by

[1] 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.

[2] 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).

[3] 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).

[4] 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.

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

[6] 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.

[7] 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).

[8] 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).

[9] M. Sohaib Alam, "Quantum Logic Gate Synthesis as a Markov Decision Process", arXiv:1912.12002.

The above citations are from Crossref's cited-by service (last updated successfully 2021-09-23 06:47:07) and SAO/NASA ADS (last updated successfully 2021-09-23 06:47:08). The list may be incomplete as not all publishers provide suitable and complete citation data.