{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T17:12:56Z","timestamp":1780765976812,"version":"3.54.1"},"reference-count":63,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T00:00:00Z","timestamp":1557705600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>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<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>U<\/mml:mi><\/mml:math>and a trainable unitary<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>V<\/mml:mi><\/mml:math>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<mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi mathvariant=\"normal\">T<\/mml:mi><mml:mi mathvariant=\"normal\">r<\/mml:mi><\/mml:mrow><mml:mo stretchy=\"false\">(<\/mml:mo><mml:msup><mml:mi>V<\/mml:mi><mml:mo>\u2020<\/mml:mo><\/mml:msup><mml:mi>U<\/mml:mi><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math>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.<\/jats:p>","DOI":"10.22331\/q-2019-05-13-140","type":"journal-article","created":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T11:42:02Z","timestamp":1557747722000},"page":"140","source":"Crossref","is-referenced-by-count":321,"title":["Quantum-assisted quantum compiling"],"prefix":"10.22331","volume":"3","author":[{"given":"Sumeet","family":"Khatri","sequence":"first","affiliation":[{"name":"Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM USA."},{"name":"Hearne Institute for Theoretical Physics and Department of Physics and Astronomy, Louisiana State University, Baton Rouge, LA USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ryan","family":"LaRose","sequence":"additional","affiliation":[{"name":"Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM USA."},{"name":"Department of Computational Mathematics, Science, and Engineering and Department of Physics and Astronomy, Michigan State University, East Lansing, MI USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Poremba","sequence":"additional","affiliation":[{"name":"Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM USA."},{"name":"Computing and Mathematical Sciences, California Institute of Technology, Pasadena, CA USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lukasz","family":"Cincio","sequence":"additional","affiliation":[{"name":"Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew T.","family":"Sornborger","sequence":"additional","affiliation":[{"name":"Information Sciences, Los Alamos National Laboratory, Los Alamos, NM USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Patrick J.","family":"Coles","sequence":"additional","affiliation":[{"name":"Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2019,5,13]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"P. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing 26, 1484 (1997).","DOI":"10.1137\/S0097539795293172"},{"key":"1","unstructured":"E. Farhi, J. Goldstone, and S. Gutmann, A quantum approximate optimization algorithm, arXiv:1411.4028 (2014)."},{"key":"2","doi-asserted-by":"publisher","unstructured":"R. P. Feynman, Simulating physics with computers, International Journal of Theoretical Physics 21, 467 (1982).","DOI":"10.1007\/BF02650179"},{"key":"3","doi-asserted-by":"publisher","unstructured":"J. Preskill, Quantum computing in the NISQ era and beyond, Quantum 2, 79 (2018).","DOI":"10.22331\/q-2018-08-06-79"},{"key":"4","unstructured":"J. Preskill, Quantum computing and the entanglement frontier, arXiv:1203.5813 (2012)."},{"key":"5","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1126\/science.aao4309"},{"key":"6","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1088\/2058-9565\/aaa331"},{"key":"7","doi-asserted-by":"crossref","unstructured":"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).","DOI":"10.1609\/icaps.v28i1.13920"},{"key":"8","doi-asserted-by":"publisher","unstructured":"L. Cincio, Y. Suba\u015fi, A. T. Sornborger, and P. J. Coles, Learning the quantum algorithm for state overlap, New Journal of Physics 20, 113022 (2018).","DOI":"10.1088\/1367-2630\/aae94a"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1109\/TCAD.2007.911334"},{"key":"10","doi-asserted-by":"crossref","unstructured":"A. G. Fowler, Constructing arbitrary Steane code single logical qubit fault-tolerant gates, Quantum Information and Computation 11, 867 (2011).","DOI":"10.26421\/QIC11.9-10-10"},{"key":"11","unstructured":"J. Booth Jr, Quantum compiler optimizations, arXiv:1206.3348 (2012)."},{"key":"12","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/s41534-018-0072-4"},{"key":"13","doi-asserted-by":"publisher","unstructured":"F. T. Chong, D. Franklin, and M. Martonosi, Programming languages and compiler design for realistic quantum hardware, Nature 549, 180 (2017).","DOI":"10.1038\/nature23459"},{"key":"14","doi-asserted-by":"publisher","unstructured":"L. E. Heyfron and E. T. Campbell, An efficient quantum compiler that reduces T count, Quantum Science and Technology 4, 015004 (2018).","DOI":"10.1088\/2058-9565\/aad604"},{"key":"15","doi-asserted-by":"publisher","unstructured":"T. H\u00e4ner, D. S. Steiger, K. Svore, and M. Troyer, A software methodology for compiling quantum programs, Quantum Science and Technology 3, 020501 (2018).","DOI":"10.1088\/2058-9565\/aaa5cc"},{"key":"16","doi-asserted-by":"crossref","unstructured":"A. Oddi and R. Rasconi, in International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (Springer, 2018) pp. 446-461.","DOI":"10.1007\/978-3-319-93031-2_32"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/ncomms5213"},{"key":"18","unstructured":"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)."},{"key":"19","doi-asserted-by":"crossref","unstructured":"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).","DOI":"10.1038\/s41534-019-0157-8"},{"key":"20","doi-asserted-by":"publisher","unstructured":"K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii, Quantum circuit learning, Physical Review A 98, 032309 (2018).","DOI":"10.1103\/PhysRevA.98.032309"},{"key":"21","unstructured":"G. Verdon, J. Pye, and M. Broughton, A Universal Training Algorithm for Quantum Deep Learning, arXiv:1806.09729 (2018)."},{"key":"22","doi-asserted-by":"publisher","unstructured":"J. Romero, J. P. Olson, and A. Aspuru-Guzik, Quantum autoencoders for efficient compression of quantum data, Quantum Science and Technology 2, 045001 (2017).","DOI":"10.1088\/2058-9565\/aa8072"},{"key":"23","unstructured":"J. Romero, J. P. Olson, and A. Aspuru-Guzik, Quantum autoencoders for short depth quantum circuit synthesis, GitHub article (2018)."},{"key":"24","doi-asserted-by":"publisher","unstructured":"B. Dive, A. Pitchford, F. Mintert, and D. Burgarth, In situ upgrade of quantum simulators to universal computers, Quantum 2, 80 (2018).","DOI":"10.22331\/q-2018-08-08-80"},{"key":"25","doi-asserted-by":"publisher","unstructured":"E. Knill and R. Laflamme, Power of one bit of quantum information, Physical Review Letters 81, 5672 (1998).","DOI":"10.1103\/PhysRevLett.81.5672"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.120.200502"},{"key":"27","doi-asserted-by":"publisher","unstructured":"B. Rosgen and J. Watrous, in 20th Annual IEEE Conference on Computational Complexity (CCC'05) (2005) pp. 344-354.","DOI":"10.1109\/CCC.2005.21"},{"key":"28","unstructured":"R. S. Smith, M. J. Curtis, and W. J. Zeng, A practical quantum instruction set architecture, arXiv:1608.03355 (2016)."},{"key":"29","unstructured":"A. W. Cross, L. S. Bishop, J. A. Smolin, and J. M. Gambetta, Open Quantum Assembly Language, arXiv:1707.03429 (2017)."},{"key":"30","doi-asserted-by":"publisher","unstructured":"M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2000).","DOI":"10.1017\/CBO9780511976667"},{"key":"31","doi-asserted-by":"publisher","unstructured":"A. Kitaev, Quantum computations: algorithms and error correction, Russian Mathematical Surveys 52, 1191 (1997).","DOI":"10.1070\/RM1997v052n06ABEH002155"},{"key":"32","doi-asserted-by":"crossref","unstructured":"C. M. Dawson and M. A. Nielsen, The Solovay-Kitaev algorithm, Quantum Information and Compututation 6, 81 (2006).","DOI":"10.26421\/QIC6.1-6"},{"key":"33","doi-asserted-by":"publisher","unstructured":"T. T. Pham, R. Van Meter, and C. Horsman, Optimization of the Solovay-Kitaev algorithm, Physical Review A 87, 052332 (2013).","DOI":"10.1103\/PhysRevA.87.052332"},{"key":"34","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.110.190502"},{"key":"35","doi-asserted-by":"publisher","unstructured":"V. Kliuchnikov, A. Bocharov, and K. M. Svore, Asymptotically optimal topological quantum compiling, Physical Review Letters 112, 140504 (2014).","DOI":"10.1103\/PhysRevLett.112.140504"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Y. Zhiyenbayev, V. M. Akulin, and A. Mandilara, Quantum compiling with diffusive sets of gates, Physical Review A 98, 012325 (2018).","DOI":"10.1103\/PhysRevA.98.012325"},{"key":"37","doi-asserted-by":"publisher","unstructured":"M. Horodecki, P. Horodecki, and R. Horodecki, General teleportation channel, singlet fraction, and quasidistillation, Physical Review A 60, 1888 (1999).","DOI":"10.1103\/PhysRevA.60.1888"},{"key":"38","doi-asserted-by":"publisher","unstructured":"M. A. Nielsen, A simple formula for the average gate fidelity of a quantum dynamical operation, Physics Letters A 303, 249 (2002).","DOI":"10.1016\/S0375-9601(02)01272-0"},{"key":"39","doi-asserted-by":"publisher","unstructured":"A. Gepp and P. Stocks, A review of procedures to evolve quantum algorithms, Genetic Programming and Evolvable Machines 10, 181 (2009).","DOI":"10.1007\/s10710-009-9080-7"},{"key":"40","doi-asserted-by":"publisher","unstructured":"M. Suzuki, Fractal decomposition of exponential operators with applications to many-body theories and monte carlo simulations, Physics Letters A 146, 319 (1990).","DOI":"10.1016\/0375-9601(90)90962-N"},{"key":"41","unstructured":"T. Jones and S. C. Benjamin, Quantum compilation and circuit optimisation via energy dissipation, arXiv:1811.03147 (2018)."},{"key":"42","doi-asserted-by":"publisher","unstructured":"J. C. Garcia-Escartin and P. Chamorro-Posada, Swap test and Hong-Ou-Mandel effect are equivalent, Physical Review A 87, 052330 (2013).","DOI":"10.1103\/PhysRevA.87.052330"},{"key":"43","doi-asserted-by":"crossref","unstructured":"P. W. Shor and S. P. Jordan, Estimating jones polynomials is a complete problem for one clean qubit, Quantum Information & Computation 8, 681 (2008).","DOI":"10.26421\/QIC8.8-9-1"},{"key":"44","unstructured":"IBM Q 5 Tenerife backend specification, (2018a)."},{"key":"45","unstructured":"IBM Q 16 Rueschlikon backend specification, (2018b)."},{"key":"46","unstructured":"Rigetti 8Q-Agave specification v.2.0.0.dev0, (2018)."},{"key":"47","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/s41467-018-07090-4"},{"key":"48","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1103\/PhysRevLett.122.020601"},{"key":"49","unstructured":"X. Glorot and Y. Bengio, in In Proceedings of the International Conference on Artificial Intelligence and Statistics (2010) pp. 249-256."},{"key":"50","doi-asserted-by":"crossref","unstructured":"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).","DOI":"10.1038\/s41534-019-0157-8"},{"key":"51","doi-asserted-by":"crossref","unstructured":"R. LaRose, A. Tikku, \u00c9. O'Neel-Judy, L. Cincio, and P. J. Coles, Variational quantum state diagonalization, arXiv:1810.10506 (2018).","DOI":"10.1038\/s41534-019-0167-6"},{"key":"52","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/s41586-019-1040-7"},{"key":"53","unstructured":"Scikit-optimize, (2018a)."},{"key":"54","doi-asserted-by":"publisher","unstructured":"J. Mo\u010dkus, in Optimization Techniques IFIP Technical Conference Novosibirsk, July 1-7, 1974 (Springer Berlin Heidelberg, Berlin, Heidelberg, 1975) pp. 400-404.","DOI":"10.1007\/978-3-662-38527-2_55"},{"key":"55","unstructured":"M. A. Osborne, R. Garnett, and S. J. Roberts, in 3rd International Conference on Learning and Intelligent Optimization (LION3) 2009 (2009)."},{"key":"56","unstructured":"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)."},{"key":"57","unstructured":"I. Kerenidis and A. Prakash, Quantum gradient descent for linear systems and least squares, arXiv:1704.04992 (2017)."},{"key":"58","doi-asserted-by":"publisher","unstructured":"A. Gily\u00e9n, 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.","DOI":"10.1137\/1.9781611975482.87"},{"key":"59","unstructured":"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)."},{"key":"60","doi-asserted-by":"publisher","unstructured":"F. Vatan and C. Williams, Optimal quantum circuits for general two-qubit gates, Physical Review A 69, 032315 (2004).","DOI":"10.1103\/PhysRevA.69.032315"},{"key":"61","unstructured":"Scipy optimization and root finding, (2018b)."},{"key":"62","doi-asserted-by":"publisher","unstructured":"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).","DOI":"10.1038\/ncomms1392"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2019-05-13-140\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,9,16]],"date-time":"2023-09-16T14:24:14Z","timestamp":1694874254000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2019-05-13-140\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,13]]},"references-count":63,"URL":"https:\/\/doi.org\/10.22331\/q-2019-05-13-140","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,13]]},"article-number":"140"}}