Abstract
This paper describes an application of the quantum approximate optimisation algorithm (QAOA) to efficiently find approximate solutions for computational problems contained in the polynomially bounded NP optimisation complexity class (NPO PB). We consider a generalisation of the QAOA state evolution to alternating quantum walks and solution-quality-dependent phase shifts and use the quantum walks to integrate the problem constraints of NPO problems. We apply the concept of a hybrid quantum-classical variational scheme to attempt finding the highest expectation value, which contains a high-quality solution. We synthesise an efficient quantum circuit for the constrained optimisation algorithm, and we numerically demonstrate the behaviour of the circuit with respect to an illustrative NP optimisation problem with constraints, minimum vertex cover. With examples, this paper demonstrates that the degree of accuracy to which the quantum walks are simulated can be treated as an additional optimisation parameter, leading to improved results.
Similar content being viewed by others
References
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26, 1484 (1997)
Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D.A.: Exponential algorithmic speedup by a quantum walk. In: STOC, p. 59. ACM (2003)
Grover, L.K.: A fast quantum mechanical algorithm for database search. In: STOC, p. 212. ACM (1996)
Farhi, E., Goldstone, J., Gutmann, S.: A Quantum Approximate Optimization Algorithm (2014). arXiv:1411.4028 [quant-ph]
Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum Computation by Adiabatic Evolution (2000). arXiv:quant-ph/0001106
Farhi, E., Gutmann, S.: Quantum computation and decision trees. Phys. Rev. A 58, 915 (1998)
Childs, A.M., Gosset, D., Webb, Z.: Universal computation by multiparticle quantum walk. Science 339, 791 (2013)
Izaac, J.A., Zhan, X., Bian, Z., Wang, K., Li, J., Wang, J.B., Xue, P.: Centrality measure based on continuous-time quantum walks and experimental realization. Phys. Rev. A 95, 032318 (2017)
Loke, T., Tang, J.W., Rodriguez, J., Small, M., Wang, J.B.: Comparing classical and quantum PageRanks. Quantum Inf. Process. 16, 25 (2017)
Gamble, J.K., Friesen, M., Zhou, D., Joynt, R., Coppersmith, S.N.: Two-particle quantum walks applied to the graph isomorphism problem. Phys. Rev. A 81, 052313 (2010)
Xu, S., Sun, X., Wu, J., Zhang, W.-W., Arshed, N., Sanders, B.C.: Quantum walk on a chimera graph. N. J. Phys. 20, 053039 (2018)
Childs, A.M., Goldstone, J.: Spatial search by quantum walk. Phys. Rev. A 70, 022314 (2004)
Li, Z.-J., Wang, J.B.: An analytical study of quantum walk through glued-tree graphs. J. Phys. A Math. Theor. 48, 355301 (2015)
Manouchehri, K., Wang, J.B.: Physical Implementation of Quantum Walks. Springer, Berlin (2014)
Qiang, X., Loke, T., Montanaro, A., Aungskunsiri, K., Zhou, X., O’Brien, J.L., Wang, J.B., Matthews, J.C.F.: Efficient quantum walk on a quantum processor. Nat. Commun. 7, 11511 (2016)
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P.J., Aspuru-Guzik, A., O’Brien, J.L.: A variational eigenvalue solver on a photonic quantum processor. Nat. Commun. 5, 4213 (2014)
Lucas, A.: Ising formulations of many np problems. Front. Phys. 2, 5 (2014)
Filiol, E., Franc, E., Gubbioli, A., Moquet, B., Roblot, G.: Combinatorial optimisation of worm propagation on an unknown network. World Acad. Sci. Eng. Technol. 23, 373 (2007)
Lancia, G., Bafna, V., Istrail, S., Lippert, R., Schwartz, R.: SNPs problems, complexity, and algorithms. In: Computers and Games, p. 182. Springer (2001)
O’Callahan, R., Choi, Jong Deok: Hybrid dynamic data race detection. ACM SIGPLAN Not. 38, 167 (2003)
Hou, Aimin: A theory of measurement in diagnosis from first principles. Artif. Intell. 65, 281 (1994)
Domingo, C., Mishra, N., Pitt, L.: Efficient read-restricted monotone CNF/DNF dualization by learning with membership queries. Mach. Learn. 37, 89 (1999)
Kann, V.: Strong lower bounds on the approximability of some NPO PB-complete maximization problems. In: Wiedermann, J., Hájek, P. (eds.) Mathematical Foundations of Computer Science, p. 227. Springer (1995)
Kann, V.: Polynomially bounded minimization problems which are hard to approximate. In: Lingas, A., Karlsson, R., Carlsson, S. (eds.) Automata, Languages and Programming, p. 52. Springer (1993)
Godsil, C.: State transfer on graphs. Discrete Math. 312, 129 (2012)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, p. 85. Springer (1972)
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E.G., Venturelli, D., Biswas, R.: From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz (2017). arXiv:1709.03489 [quant-ph]
Feller, W.: The fundamental limit theorems in probability. Bull. Am. Math. Soc 51, 800 (1945)
Sharma, R., Gupta, M., Kapoor, G.: Some better bounds on the variance with applications. J. Math. Inequal. 4, 355 (2010)
Welch, J., Greenbaum, D., Mostame, S., Aspuru-Guzik, A.: Efficient quantum circuits for diagonal unitaries without ancillas. N. J. Phys. 16, 033040 (2014)
Childs, A.M.: Quantum information processing in continuous time. Ph.D. thesis, Massachusetts Institute of Technology (2004)
Aharonov, D., Ta-Shma, A.: Adiabatic quantum state generation and statistical zero knowledge. In: STOC, p. 20. ACM (2003)
Suzuki, M.: General theory of higher-order decomposition of exponential operators and symplectic integrators. Phys. Lett. A 165, 387 (1992)
Lau, H.-K., Pooser, R., Siopsis, G., Weedbrook, C.: Quantum machine learning over infinite dimensions. Phys. Rev. Lett. 118, 080501 (2017)
Google. Cirq. https://github.com/quantumlib/Cirq (2018). Accessed 30 Oct 2018
Nelder, J.A., Mead, R.: A simplex method for function minimization. Comput. J. 7, 308 (1965)
Erdős, P., Rényi, A.: On random graphs. I. Publ. Math. 6, 290 (1959)
Acknowledgements
This research was supported by a Hackett Postgraduate Research Scholarship and an Australian Government Research Training Program Scholarship at the University of Western Australia. We thank Lyle Noakes for his helpful comments and discussions.
Author information
Authors and Affiliations
Corresponding author
Appendix A: Numerical results for random graphs
Appendix A: Numerical results for random graphs
Classical simulations of the quantum state evolution were performed to evaluate the quality of approximate solutions in the context of minimum vertex cover. We define the approximation quality for a particular problem instance as the ratio of the number of vertices in the minimum vertex cover to the approximate cover. Since for a n-qubit quantum register the classical computer must store all \(2^n\) quantum amplitudes in memory, results were obtained for only low-n simulations (\(\lesssim 20\)). To reduce the computational cost, the state evolution is carried out by direct computation and multiplication of the matrices \(e^{-i \gamma {\hat{C}}}\) and \(e^{-i \beta {\hat{B}}}\), rather than simulating the quantum circuit. As in Sect. 5, the Nelder–Mead nonlinear optimiser [36] is used to optimise the expectation value \(F_p(\vec {\beta }, \vec {\gamma })\).
The performance of the \(p=2\) algorithm was tested on a random sample of G(n, 0.5) Erdős–Rényi graphs. The G(n, 0.5) Erdős–Rényi random graph model [37] has equal probability to select each of the \(2^{n(n-1)/2}\) n-vertex graphs, so it gives a good impression of the ‘average case’ performance of the heuristic. The solution qualities for each random graph are shown in Fig. 10, with 20 instances considered per n. Taking \(n=5\) as an example, the optimal vertex cover is found for all but two random instances tested. The solution quality decreases reasonably slowly, and for all trialled graphs the produced solution used at most 1.6 times the number of vertices as the optimal solution.
Note that the results in this ‘Appendix’ are an exact simulation of the desired QAOA state evolution, rather than a simulation of the quantum circuit. Hence, the results here are specific to the case \(m \rightarrow \infty \), where m is the ‘walk simulation accuracy’ parameter introduced in Sect. 4.3. The solution qualities would be further improved by optimising over this parameter.
Rights and permissions
About this article
Cite this article
Marsh, S., Wang, J.B. A quantum walk-assisted approximate algorithm for bounded NP optimisation problems. Quantum Inf Process 18, 61 (2019). https://doi.org/10.1007/s11128-019-2171-3
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11128-019-2171-3