Quantum-assisted quantum compiling

Sumeet Khatri1,2, Ryan LaRose1,3, Alexander Poremba1,4, Lukasz Cincio1, Andrew T. Sornborger5, and Patrick J. Coles1

1Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM USA.
2Hearne Institute for Theoretical Physics and Department of Physics and Astronomy, Louisiana State University, Baton Rouge, LA USA.
3Department of Computational Mathematics, Science, and Engineering and Department of Physics and Astronomy, Michigan State University, East Lansing, MI USA.
4Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA USA.
5Information Sciences, Los Alamos National Laboratory, Los Alamos, NM USA.

Compiling quantum algorithms for near-term quantum computers (accounting for connectivity and native gate alphabets) is a major challenge that has received significant attention both by industry and academia. Avoiding the exponential overhead of classical simulation of quantum dynamics will allow compilation of larger algorithms, and a strategy for this is to evaluate an algorithm's cost on a quantum computer. To this end, we propose a variational hybrid quantum-classical algorithm called quantum-assisted quantum compiling (QAQC). In QAQC, we use the overlap between a target unitary $U$ and a trainable unitary $V$ as the cost function to be evaluated on the quantum computer. More precisely, to ensure that QAQC scales well with problem size, our cost involves not only the global overlap ${\rm Tr}(V^†U)$ but also the local overlaps with respect to individual qubits. We introduce novel short-depth quantum circuits to quantify the terms in our cost function, and we prove that our cost cannot be efficiently approximated with a classical algorithm under reasonable complexity assumptions. We present both gradient-free and gradient-based approaches to minimizing this cost. As a demonstration of QAQC, we compile various one-qubit gates on IBM's and Rigetti's quantum computers into their respective native gate alphabets. Furthermore, we successfully simulate QAQC up to a problem size of 9 qubits, and these simulations highlight both the scalability of our cost function as well as the noise resilience of QAQC. Future applications of QAQC include algorithm depth compression, black-box compiling, noise mitigation, and benchmarking.

Ordinary computers require a compiler that converts one's code into a machine-level language. Quantum computers require a compiler as well. However, a new challenge for such "quantum compilers" is that they should be optimal, i.e., they should return a machine-level program that has as few operations as possible. This optimality is crucial for current noisy quantum devices, where longer programs accumulate more errors while shorter programs avoid errors. In this work, we introduce an algorithm for optimal quantum compiling. The key feature that allows for optimality is that we propose to use quantum computers themselves to assist in the compiling process. Hence, our algorithm is called quantum-assisted quantum compiling (QAQC, pronounced "Quack").

The idea is that one needs to quantify the distance between the original program and the compiled program, with the goal of trying to minimize this distance. We prove that this distance calculation cannot be done efficiently on a classical computer. On the other hand, we provide an efficient quantum circuit for computing it.

In addition to shortening the length of one's quantum program, QAQC can be used to learn algorithms that compensate for a given quantum computer's noise and also to benchmark the noise processes occurring on a quantum computer. We successfully implement QAQC for small programs using currently available quantum computers from IBM and Rigetti, and we use simulators to explore the compilation of larger programs. Overall, QAQC appears to be a promising tool for mitigating errors in the era of noisy intermediate-scale quantum computers.

► BibTeX data

► References

[1] P. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing 26, 1484 (1997).
https:/​/​doi.org/​10.1137/​S0097539795293172

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

[3] R. P. Feynman, Simulating physics with computers, International Journal of Theoretical Physics 21, 467 (1982).
https:/​/​doi.org/​10.1007/​BF02650179

[4] J. Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[5] J. Preskill, Quantum computing and the entanglement frontier, arXiv:1203.5813 (2012).
arXiv:1203.5813

[6] C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, S. V. Isakov, V. Smelyanskiy, et al., A blueprint for demonstrating quantum supremacy with superconducting qubits, Science 360, 195 (2018).
https:/​/​doi.org/​10.1126/​science.aao4309

[7] D. Venturelli, M. Do, E. Rieffel, and J. Frank, Compiling quantum circuits to realistic hardware architectures using temporal planners, Quantum Science and Technology 3, 025004 (2018).
https:/​/​doi.org/​10.1088/​2058-9565/​aaa331

[8] K. E. C. Booth, M. Do, J. C. Beck, E. Rieffel, D. Venturelli, and J. Frank, Comparing and integrating constraint programming and temporal planning for quantum circuit compilation, arXiv:1803.06775 (2018).
arXiv:1803.06775

[9] L. Cincio, Y. Subaşi, A. T. Sornborger, and P. J. Coles, Learning the quantum algorithm for state overlap, New Journal of Physics 20, 113022 (2018).
https:/​/​doi.org/​10.1088/​1367-2630/​aae94a

[10] D. Maslov, G. W. Dueck, D. M. Miller, and C. Negrevergne, Quantum circuit simplification and level compaction, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27, 436 (2008).
https:/​/​doi.org/​10.1109/​TCAD.2007.911334

[11] A. G. Fowler, Constructing arbitrary Steane code single logical qubit fault-tolerant gates, Quantum Information and Computation 11, 867 (2011).
http:/​/​dl.acm.org/​citation.cfm?id=2230936.2230946

[12] J. Booth Jr, Quantum compiler optimizations, arXiv:1206.3348 (2012).
arXiv:1206.3348

[13] Y. Nam, N. J. Ross, Y. Su, A. M. Childs, and D. Maslov, Automated optimization of large quantum circuits with continuous parameters, npj Quantum Information 4, 23 (2018).
https:/​/​doi.org/​10.1038/​s41534-018-0072-4

[14] F. T. Chong, D. Franklin, and M. Martonosi, Programming languages and compiler design for realistic quantum hardware, Nature 549, 180 (2017).
https:/​/​doi.org/​10.1038/​nature23459

[15] L. E. Heyfron and E. T. Campbell, An efficient quantum compiler that reduces T count, Quantum Science and Technology 4, 015004 (2018).
https:/​/​doi.org/​10.1088/​2058-9565/​aad604

[16] T. Häner, D. S. Steiger, K. Svore, and M. Troyer, A software methodology for compiling quantum programs, Quantum Science and Technology 3, 020501 (2018).
https:/​/​doi.org/​10.1088/​2058-9565/​aaa5cc

[17] A. Oddi and R. Rasconi, in International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (Springer, 2018) pp. 446-461.
https:/​/​link.springer.com/​chapter/​10.1007/​978-3-319-93031-2_32

[18] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O'Brien, A variational eigenvalue solver on a photonic quantum processor, Nature Communications 5, 4213 (2014).
https:/​/​doi.org/​10.1038/​ncomms5213

[19] P. D. Johnson, J. Romero, J. Olson, Y. Cao, and A. Aspuru-Guzik, QVECTOR: an algorithm for device-tailored quantum error correction, arXiv:1711.02249 (2017).
arXiv:1711.02249

[20] M. Benedetti, D. Garcia-Pintos, O. Perdomo, V. Leyton-Ortega, Y. Nam, and A. Perdomo-Ortiz, A generative modeling approach for benchmarking and training shallow quantum circuits, arXiv:1801.07686 (2018a).
arXiv:1801.07686

[21] K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, Quantum circuit learning, Physical Review A 98, 032309 (2018).
https:/​/​doi.org/​10.1103/​PhysRevA.98.032309

[22] G. Verdon, J. Pye, and M. Broughton, A Universal Training Algorithm for Quantum Deep Learning, arXiv:1806.09729 (2018).
arXiv:1806.09729

[23] J. Romero, J. P. Olson, and A. Aspuru-Guzik, Quantum autoencoders for efficient compression of quantum data, Quantum Science and Technology 2, 045001 (2017).
https:/​/​doi.org/​10.1088/​2058-9565/​aa8072

[24] J. Romero, J. P. Olson, and A. Aspuru-Guzik, Quantum autoencoders for short depth quantum circuit synthesis, GitHub article (2018).
https:/​/​github.com/​zapatacomputing/​cusp_cirq_demo/​blob/​master/​cusp_protocol.pdf

[25] B. Dive, A. Pitchford, F. Mintert, and D. Burgarth, In situ upgrade of quantum simulators to universal computers, Quantum 2, 80 (2018).
https:/​/​doi.org/​10.22331/​q-2018-08-08-80

[26] E. Knill and R. Laflamme, Power of one bit of quantum information, Physical Review Letters 81, 5672 (1998).
https:/​/​doi.org/​10.1103/​PhysRevLett.81.5672

[27] K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani, Impossibility of Classically Simulating One-Clean-Qubit Model with Multiplicative Error, Physical Review Letters 120, 200502 (2018).
https:/​/​doi.org/​10.1103/​PhysRevLett.120.200502

[28] B. Rosgen and J. Watrous, in 20th Annual IEEE Conference on Computational Complexity (CCC'05) (2005) pp. 344-354.
https:/​/​doi.org/​10.1109/​CCC.2005.21

[29] R. S. Smith, M. J. Curtis, and W. J. Zeng, A practical quantum instruction set architecture, arXiv:1608.03355 (2016).
arXiv:1608.03355

[30] A. W. Cross, L. S. Bishop, J. A. Smolin, and J. M. Gambetta, Open Quantum Assembly Language, arXiv:1707.03429 (2017).
arXiv:1707.03429

[31] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2000).
https:/​/​doi.org/​10.1017/​CBO9780511976667

[32] A. Kitaev, Quantum computations: algorithms and error correction, Russian Mathematical Surveys 52, 1191 (1997).
https:/​/​doi.org/​10.1070/​RM1997v052n06ABEH002155

[33] C. M. Dawson and M. A. Nielsen, The Solovay-Kitaev algorithm, Quantum Information and Compututation 6, 81 (2006).
http:/​/​dl.acm.org/​citation.cfm?id=2011679.2011685

[34] T. T. Pham, R. Van Meter, and C. Horsman, Optimization of the Solovay-Kitaev algorithm, Physical Review A 87, 052332 (2013).
https:/​/​doi.org/​10.1103/​PhysRevA.87.052332

[35] V. Kliuchnikov, D. Maslov, and M. Mosca, Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits, Physical Review Letters 110, 190502 (2013).
https:/​/​doi.org/​10.1103/​PhysRevLett.110.190502

[36] V. Kliuchnikov, A. Bocharov, and K. M. Svore, Asymptotically optimal topological quantum compiling, Physical Review Letters 112, 140504 (2014).
https:/​/​doi.org/​10.1103/​PhysRevLett.112.140504

[37] Y. Zhiyenbayev, V. M. Akulin, and A. Mandilara, Quantum compiling with diffusive sets of gates, Physical Review A 98, 012325 (2018).
https:/​/​doi.org/​10.1103/​PhysRevA.98.012325

[38] M. Horodecki, P. Horodecki, and R. Horodecki, General teleportation channel, singlet fraction, and quasidistillation, Physical Review A 60, 1888 (1999).
https:/​/​doi.org/​10.1103/​PhysRevA.60.1888

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

[40] A. Gepp and P. Stocks, A review of procedures to evolve quantum algorithms, Genetic Programming and Evolvable Machines 10, 181 (2009).
https:/​/​doi.org/​10.1007/​s10710-009-9080-7

[41] M. Suzuki, Fractal decomposition of exponential operators with applications to many-body theories and monte carlo simulations, Physics Letters A 146, 319 (1990).
https:/​/​doi.org/​10.1016/​0375-9601(90)90962-N

[42] T. Jones and S. C. Benjamin, Quantum compilation and circuit optimisation via energy dissipation, arXiv:1811.03147 (2018).
arXiv:1811.03147

[43] J. C. Garcia-Escartin and P. Chamorro-Posada, Swap test and Hong-Ou-Mandel effect are equivalent, Physical Review A 87, 052330 (2013).
https:/​/​doi.org/​10.1103/​PhysRevA.87.052330

[44] P. W. Shor and S. P. Jordan, Estimating jones polynomials is a complete problem for one clean qubit, Quantum Information & Computation 8, 681 (2008).
http:/​/​www.rintonpress.com/​xxqic8/​qic-8-89/​0681-0714.pdf

[45] IBM Q 5 Tenerife backend specification, (2018a).
https:/​/​github.com/​QISKit/​qiskit-backend-information/​tree/​master/​backends/​tenerife/​V1

[46] IBM Q 16 Rueschlikon backend specification, (2018b).
https:/​/​github.com/​Qiskit/​qiskit-backend-information/​tree/​master/​backends/​rueschlikon/​V1

[47] Rigetti 8Q-Agave specification v.2.0.0.dev0, (2018).
http:/​/​docs.rigetti.com/​en/​latest/​qpu.html

[48] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, Barren plateaus in quantum neural network training landscapes, Nature Communications 9, 4812 (2018).
https:/​/​doi.org/​10.1038/​s41467-018-07090-4

[49] A. G. R. Day, M. Bukov, P. Weinberg, P. Mehta, and D. Sels, Glassy phase of optimal quantum control, Physical Review Letters 122, 020601 (2019).
https:/​/​doi.org/​10.1103/​PhysRevLett.122.020601

[50] X. Glorot and Y. Bengio, in In Proceedings of the International Conference on Artificial Intelligence and Statistics (2010) pp. 249-256.
http:/​/​proceedings.mlr.press/​v9/​glorot10a/​glorot10a.pdf?hc_location=ufi

[51] M. Benedetti, D. Garcia-Pintos, O. Perdomo, V. Leyton-Ortega, Y. Nam, and A. Perdomo-Ortiz, A generative modeling approach for benchmarking and training shallow quantum circuits, arXiv:1801.07686 (2018b).
arXiv:1801.07686

[52] R. LaRose, A. Tikku, É. O'Neel-Judy, L. Cincio, and P. J. Coles, Variational quantum state diagonalization, arXiv:1810.10506 (2018).
arXiv:1810.10506

[53] A. Kandala, K. Temme, A. D. Corcoles, A. Mezzacapo, J. M. Chow, and J. M. Gambetta, Extending the computational reach of a noisy superconducting quantum processor, Nature 567, 491 (2018).
https:/​/​doi.org/​10.1038/​s41586-019-1040-7

[54] Scikit-optimize, (2018a).
https:/​/​github.com/​scikit-optimize/​scikit-optimize

[55] J. Močkus, in Optimization Techniques IFIP Technical Conference Novosibirsk, July 1-7, 1974 (Springer Berlin Heidelberg, Berlin, Heidelberg, 1975) pp. 400-404.
https:/​/​doi.org/​10.1007/​978-3-662-38527-2_55

[56] M. A. Osborne, R. Garnett, and S. J. Roberts, in 3rd International Conference on Learning and Intelligent Optimization (LION3) 2009 (2009).
https:/​/​www.cse.wustl.edu/​~garnett/​files/​papers/​osborne_et_al_lion_2009.pdf

[57] P. Rebentrost, M. Schuld, L. Wossnig, F. Petruccione, and S. Lloyd, Quantum gradient descent and Newton's method for constrained polynomial optimization, arXiv:1612.01789 (2016).
arXiv:1612.01789

[58] I. Kerenidis and A. Prakash, Quantum gradient descent for linear systems and least squares, arXiv:1704.04992 (2017).
arXiv:1704.04992

[59] A. Gilyén, S. Arunachalam, and N. Wiebe, Optimizing quantum optimization algorithms via faster quantum gradient computation, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1425-1444.
https:/​/​doi.org/​10.1137/​1.9781611975482.87

[60] P. B. M. Sousa and R. V. Ramos, Universal quantum circuit for $n$-qubit quantum gate: A programmable quantum gate, Quantum Information and Computation 7, 228 (2007).
http:/​/​dl.acm.org/​citation.cfm?id=2011717.2011721

[61] F. Vatan and C. Williams, Optimal quantum circuits for general two-qubit gates, Physical Review A 69, 032315 (2004).
https:/​/​doi.org/​10.1103/​PhysRevA.69.032315

[62] Scipy optimization and root finding, (2018b).
https:/​/​docs.scipy.org/​doc/​scipy/​reference/​optimize.html

[63] X.-Q. Zhou, T. C. Ralph, P. Kalasuwan, M. Zhang, A. Peruzzo, B. P. Lanyon, and J. L. O'Brien, Adding control to arbitrary unknown quantum operations, Nature Communications 2, 413 (2011).
https:/​/​doi.org/​10.1038/​ncomms1392

Cited by

[1] Ryan LaRose, Arkin Tikku, Étude O’Neel-Judy, Lukasz Cincio, and Patrick J. Coles, "Variational quantum state diagonalization", npj Quantum Information 5 1, 57 (2019).

[2] Kentaro Heya, Yasunari Suzuki, Yasunobu Nakamura, and Keisuke Fujii, "Variational Quantum Gate Optimization", arXiv:1810.12745.

[3] Andrew Arrasmith, Lukasz Cincio, Andrew T. Sornborger, Wojciech H. Zurek, and Patrick J. Coles, "Variational Consistent Histories: A Hybrid Algorithm for Quantum Foundations", arXiv:1812.10759.

[4] Maria Schuld, Ville Bergholm, Christian Gogolin, Josh Izaac, and Nathan Killoran, "Evaluating analytic gradients on quantum hardware", Physical Review A 99 3, 032331 (2019).

[5] Alexey Uvarov, Andrey Kardashin, and Jacob Biamonte, "Machine Learning Phase Transitions with a Quantum Processor", arXiv:1906.10155.

[6] Brian Coyle, Daniel Mills, Vincent Danos, and Elham Kashefi, "The Born Supremacy: Quantum Advantage and Training of an Ising Born Machine", arXiv:1904.02214.

[7] Lukasz Cincio, Yiğit Subașı, Andrew T. Sornborger, and Patrick J. Coles, "Learning the quantum algorithm for state overlap", New Journal of Physics 20 11, 113022 (2018).

[8] Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas P. D. Sawaya, Sukin Sim, Libor Veis, and Alán Aspuru-Guzik, "Quantum Chemistry in the Age of Quantum Computing", arXiv:1812.09976.

The above citations are from Crossref's cited-by service (last updated 2019-07-15 15:12:54) and SAO/NASA ADS (last updated 2019-07-15 15:12:55). The list may be incomplete as not all publishers provide suitable and complete citation data.