Two-Qubit Circuit Depth 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.

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.

► 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.
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, Sep 2018, http:/​/​arxiv.org/​abs/​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, http:/​/​arxiv.org/​abs/​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/​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/​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, Jun 2001, http:/​/​arxiv.org/​abs/​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. Dec. 1996, https:/​/​arxiv.org/​abs/​dg-ga/​9612018.
https:/​/​arxiv.org/​abs/​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/​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, http:/​/​arxiv.org/​abs/​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, Mar 2003, http:/​/​arxiv.org/​abs/​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, July 2004, http:/​/​arxiv.org/​abs/​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. Aug. 2016, http:/​/​arxiv.org/​abs/​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. , Jul 2004, http:/​/​arxiv.org/​abs/​quant-ph/​0312193. 10.1103/​PhysRevLett.93.020502.
https:/​/​doi.org/​10.1103/​PhysRevLett.93.020502
arXiv:quant-ph/0312193

Cited by

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

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

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

[4] Seyon Sivarajah, Silas Dilkes, Alexander Cowtan, Will Simmons, Alec Edgington, and Ross Duncan, "t$|$ket$\rangle$ : A Retargetable Compiler for NISQ Devices", arXiv:2003.10611.

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

The above citations are from SAO/NASA ADS (last updated successfully 2020-03-29 23:30:55). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2020-03-29 23:30:54).