Quantum circuit design for objective function maximization in gate-model quantum computers. (English) Zbl 1508.81459
Summary: Gate-model quantum computers provide an experimentally implementable architecture for near-term quantum computations. To design a reduced quantum circuit that can simulate a high-complexity reference quantum circuit, an optimization should be taken on the number of input quantum states, on the unitary operations of the quantum circuit, and on the number of output measurement rounds. Besides the optimization of the physical layout of the hardware layer, the quantum computer should also solve difficult computational problems very efficiently. To yield a desired output system, a particular objective function associated with the computational problem fed into the quantum computer should be maximized. The reduced gate structure should be able to produce the maximized value of the objective function. These parallel requirements must be satisfied simultaneously, which makes the optimization difficult. Here, we demonstrate a method for designing quantum circuits for gate-model quantum computers and define the Quantum Triple Annealing Minimization (QTAM) algorithm. The aim of QTAM is to determine an optimal reduced topology for the quantum circuits in the hardware layer at the maximization of the objective function of an arbitrary computational problem.
Software:
NSGA-IIReferences:
| [1] | Moore, G.E.: Cramming more components onto integrated circuits. Electronics (1965) · Zbl 1529.68033 |
| [2] | Ofek, N., et al.: Extending the lifetime of a quantum bit with error correction in superconducting circuits. Nature 536, 441-445 (2016) · doi:10.1038/nature18949 |
| [3] | Debnath, S., et al.: Demonstration of a small programmable quantum computer with atomic qubits. Nature 536, 63-66 (2016) · doi:10.1038/nature18648 |
| [4] | Barends, R., et al.: Superconducting quantum circuits at the surface code threshold for fault tolerance. Nature 508, 500-503 (2014) · doi:10.1038/nature13171 |
| [5] | Monz, T., et al.: Realization of a scalable Shor algorithm. Science 351, 1068-1070 (2016) · Zbl 1355.81060 · doi:10.1126/science.aad9480 |
| [6] | DiCarlo, L., et al.: Demonstration of two-qubit algorithms with a superconducting quantum processor. Nature 460, 240-244 (2009) · doi:10.1038/nature08121 |
| [7] | Higgins, B.L., Berry, D.W., Bartlett, S.D., Wiseman, H.M., Pryde, G.J.: Entanglement-free Heisenberg-limited phase estimation. Nature 450, 393-396 (2007) · doi:10.1038/nature06257 |
| [8] | Vandersypen, L.M.K., et al.: Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance. Nature 414, 883-887 (2001) · doi:10.1038/414883a |
| [9] | Gulde, S., et al.: Implementation of the Deutsch-Jozsa algorithm on an ion-trap quantum computer. Nature 421, 48-50 (2003) · doi:10.1038/nature01336 |
| [10] | IBM.: A new way of thinking: the IBM quantum experience. http://www.research.ibm.com/quantum (2017) |
| [11] | Gyongyosi, L., Imre, S., Nguyen, H.V.: A survey on quantum channel capacities. IEEE Commun. Surv. Tutorials 99, 1 (2018). https://doi.org/10.1109/COMST.2017.2786748 · doi:10.1109/COMST.2017.2786748 |
| [12] | Biamonte, J., et al.: Quantum machine learning. Nature 549, 195-202 (2017) · doi:10.1038/nature23474 |
| [13] | Lloyd, S., Mohseni, M., Rebentrost, P.: Quantum principal component analysis. Nat. Phys. 10, 631 (2014) · doi:10.1038/nphys3029 |
| [14] | Sheng, Y.B., Zhou, L.: Distributed secure quantum machine learning. Science 62, 1025-2019 (2017) |
| [15] | Kimble, H.J.: The quantum Internet. Nature 453, 1023-1030 (2008) · doi:10.1038/nature07127 |
| [16] | Farhi, E., Neven, H.: Classification with Quantum Neural Networks on Near Term Processors. arXiv:1802.06002v1 (2018) |
| [17] | Farhi, E., Goldstone, J., Gutmann, S., Neven, H.: Quantum Algorithms for Fixed Qubit Architectures. arXiv:1703.06199v1 (2017) |
| [18] | Farhi, E., Goldstone, J., Gutmann, S.: A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 (2014) · Zbl 1213.68284 |
| [19] | Farhi, E., Goldstone, J., Gutmann, S.: A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem. arXiv:1412.6062 (2014) |
| [20] | Farhi, E., Harrow, A.W.: Quantum Supremacy Through the Quantum Approximate Optimization Algorithm. arxiv:1602.07674 (2016) |
| [21] | Lloyd, S., Shapiro, J.H., Wong, F.N.C., Kumar, P., Shahriar, S.M., Yuen, H.P.: Infrastructure for the quantum Internet. ACM SIGCOMM Comput. Commun. Rev. 34, 9-20 (2004) · doi:10.1145/1039111.1039118 |
| [22] | Van Meter, R.: Quantum Networking. Wiley (2014). ISBN 1118648927, 9781118648926 · Zbl 1303.81006 |
| [23] | Gyongyosi, L., Imre, S.: Advanced Quantum Communications—An Engineering Approach. Wiley-IEEE Press, Hoboken (2012) · Zbl 1388.81001 |
| [24] | Lloyd, S. Mohseni, M., Rebentrost, P.: Quantum algorithms for supervised and unsupervised machine learning. arXiv:1307.0411 (2013) |
| [25] | Pirandola, S., Laurenza, R., Ottaviani, C., Banchi, L.: Fundamental limits of repeaterless quantum communications. Nat. Commun. 8, 15043 (2017) · doi:10.1038/ncomms15043 |
| [26] | Pirandola, S., Braunstein, S.L., Laurenza, R., Ottaviani, C., Cope, T.P.W., Spedalieri, G., Banchi, L.: Theory of channel simulation and bounds for private communication. Quantum Sci. Technol. 3, 035009 (2018) · doi:10.1088/2058-9565/aac394 |
| [27] | Martins, R., Lourenco, N., Horta, N.: Analog Integrated Circuit Design Automation. Springer (2017). ISBN 978-3-319-34059-3, ISBN 978-3-319-34060-9 |
| [28] | Martins, R., Lourenco, N., Horta, N.: Multi-objective optimization of analog integrated circuit placement hierarchy in absolute coordinates. Expert Syst. Appl. 42(23), 9137-9151 (2015) · doi:10.1016/j.eswa.2015.08.020 |
| [29] | Martins, R., Povoa, R., Lourenco, N., Horta, N.: Current-flow & current-density-aware multiobjective optimization of analog IC placement. Integr. VLSI J. (2016) |
| [30] | Bandyopadhyay, S., Saha, S., Maulik, U., Deb, K.: A simulated annealing-based multiobjective optimization algorithm: AMOSA. IEEE Trans. Evol. Comput. 12(3), 269-283 (2008) · doi:10.1109/TEVC.2007.900837 |
| [31] | Suman, B., Kumar, P.: A survey of simulated annealing as a tool for single and multiobjective optimization. J. Oper. Res. Soc. 57, 1143-1160 (2006) · Zbl 1121.90065 · doi:10.1057/palgrave.jors.2602068 |
| [32] | Jiang, I., Chang, H.Y., Chang, C.L.: WiT: optimal wiring topology for electromigration avoidance. IEEE Trans. Very Large Scale Integr. Syst. 20(4), 581-592 (2012) · doi:10.1109/TVLSI.2011.2116049 |
| [33] | Rocha, F.A.E.R.M., Martins, F., Lourenco, N.C.C., Horta, N.C.G.: Electronic Design Automation of Analog ICs, Combining Gradient Models with Multi-Objective Evolutionary Algorithms. Springer, Heidelberg (2014) · doi:10.1007/978-3-319-02189-8 |
| [34] | Perkowski, M., Lukac, M., Kerntopf, P., Pivtoraiko, M., Folgheraiter, M., Choi, Y.W., Jung-wook, K., Lee, D., Hwangbo, W., Kim, H.: A hierarchical approach to computer-aided design of quantum circuits. Electrical and Computer Engineering Faculty Publications and Presentations 228 (2003) |
| [35] | Bravyi, S., Browne, D., Calpin, P., Campbell, E., Gosset, D., Howard, M.: Simulation of quantum circuits by low-rank stabilizer decompositions. arXiv:1808.00128 (2018) |
| [36] | Munoz-Coreas, E., Thapliyal, H.: Quantum circuit design of a T-count optimized integer multiplier. IEEE Trans. Comput. (2018). https://doi.org/10.1109/TC.2018.2882774 · doi:10.1109/TC.2018.2882774 |
| [37] | Gosset, D., Kliuchnikov, V., Mosca, M., Russo, V.: An algorithm for the t-count. Quantum Inf. Comput. 14(15-16), 1261-1276 (2014) |
| [38] | Thapliyal, H., Munoz-Coreas, E., Varun, T.S.S., Humble, T.S.: Quantum circuit designs of integer division optimizing T-count and T-depth. arXiv:1809.09732 (2018) |
| [39] | Jamal, L., Babu, H.M.H.: Efficient approaches to design a reversible floating point divider. In: 2013 IEEE International Symposium on Circuits and Systems (ISCAS2013), pp. 3004-3007 (2013) |
| [40] | Zhou, X., Leung, D.W., Chuang, I.L.: Methodology for quantum logic gate construction. Phys. Rev. A 62, 052316 (2000) · doi:10.1103/PhysRevA.62.052316 |
| [41] | Gottesman, D., Chuang, I.L.: Quantum teleportation is a universal computational primitive. Nature 402, 390-393 (1999) · doi:10.1038/46503 |
| [42] | Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 32(6), 818-830 (2013) · doi:10.1109/TCAD.2013.2244643 |
| [43] | Paler, A., Polian, I., Nemoto, K., Devitt, S.J.: Fault-tolerant, high level quantum circuits: form, compilation and description. Quantum Sci. Technol. 2(2), 025003 (2017) · doi:10.1088/2058-9565/aa66eb |
| [44] | Brandao, F.G.S.L., Broughton, M., Farhi, E., Gutmann, S., Neven, H.: For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances. arXiv:1812.04170 (2018) |
| [45] | Zhou, L., Wang, S.-T., Choi, S., Pichler, H., Lukin, M.D.: Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices. arXiv:1812.01041 (2018) |
| [46] | Lechner, W.: Quantum approximate optimization with parallelizable gates. arXiv:1802.01157v2 (2018) |
| [47] | Crooks, G.E.: Performance of the quantum approximate optimization algorithm on the maximum cut problem. arXiv:1811.08419 (2018) |
| [48] | Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115 (1995) · Zbl 0885.68088 · doi:10.1145/227683.227684 |
| [49] | Ho, W.W., Jonay, C., Hsieh, T.H.: ultrafast state preparation via the quantum approximate optimization algorithm with long range interactions. arXiv:1810.04817 (2018) |
| [50] | Song, C., et al.: 10-Qubit entanglement and parallel logic operations with a superconducting circuit. Phys. Rev. Lett. 119(18), 180511 (2017) · doi:10.1103/PhysRevLett.119.180511 |
| [51] | Preskill, J.: Quantum computing in the NISQ era and beyond. Quantum 2, 79 (2018) · doi:10.22331/q-2018-08-06-79 |
| [52] | Harrow, A.W., Montanaro, A.: Quantum computational supremacy. Nature 549, 203-209 (2017) · doi:10.1038/nature23458 |
| [53] | Aaronson, S., Chen, L.: Complexity-theoretic foundations of quantum supremacy experiments. In: Proceedings of the 32nd Computational Complexity Conference, CCC ’17, pp. 22:1-22:67 (2017) · Zbl 1451.81157 |
| [54] | Gyongyosi, L., Imre, S.: A survey on quantum computing technology. In: Computer Science Review. Elsevier (2018). https://doi.org/10.1016/j.cosrev.2018.11.002. ISSN: 1574-0137 · Zbl 1409.81025 · doi:10.1016/j.cosrev.2018.11.002 |
| [55] | Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182-197 (2002) · doi:10.1109/4235.996017 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
