×

A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles. (English) Zbl 1431.81044

Summary: Recent works have shown that quantum computers can polynomially speed up certain SAT-solving algorithms even when the number of available qubits is significantly smaller than the number of variables. Here, we generalize this approach. We present a framework for hybrid quantum-classical algorithms which utilize quantum computers significantly smaller than the problem size. Given an arbitrarily small ratio of the quantum computer to the instance size, we achieve polynomial speedups for classical divide-and-conquer algorithms, provided that certain criteria on the time- and space-efficiency are met. We demonstrate how this approach can be used to enhance Eppstein’s algorithm for the cubic Hamiltonian cycle problem and achieve a polynomial speedup for any ratio of the number of qubits to the size of the graph.
©2020 American Institute of Physics

MSC:

81P68 Quantum computation
81Q93 Quantum control
93C30 Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Dunjko, V.; Ge, Y.; Cirac, J. I., Phys. Rev. Lett., 121, 250501 (2018) · doi:10.1103/physrevlett.121.250501
[2] Note that since reductions of one NP-complete problem to another generally incur significant polynomial slowdowns, and we only expect polynomial speedups, a speedup for 3SAT does not imply a speedup for other NP-complete problems. Consequently, each problem and algorithm must be treated individually.
[3] Bravyi, S.; Smith, G.; Smolin, J. A., Phys. Rev. X, 6, 021043 (2016) · doi:10.1103/physrevx.6.021043
[4] Peng, T.; Harrow, A.; Ozols, M.; Wu, X., Simulating large quantum circuits on a small quantum computer (2019)
[5] Eppstein, D., J. Graph Algorithms Appl., 11, 61 (2007) · Zbl 1161.68662 · doi:10.7155/jgaa.00137
[6] Moylett, D. J.; Linden, N.; Montanaro, A., Phys. Rev. A, 95, 032323 (2017) · doi:10.1103/physreva.95.032323
[7] Many algorithms that are not a priori given in this form can be formulated as such.
[8] For simplicity, we formulate the divide-and-conquer hybrid approach for decision problems here. The approach can be generalized to algorithms with more general outputs, subject to size constraints of the output.
[9] In general, the recursive algorithm can also take additional parameters, but these can be incorporated into P.
[10] Bentley, J. L.; Haken, D.; Saxe, J. B., SIGACT News, 12, 36 (1980) · Zbl 0451.68038 · doi:10.1145/1008861.1008865
[11] Ambainis, A., SIGACT News, 35, 22 (2004) · doi:10.1145/992287.992296
[12] Moser, R. A.; Scheder, D., 245-252 (2011), ACM: ACM, New York, NY, USA · Zbl 1288.68245
[13] Dantsin, E.; Goerdt, A.; Hirsch, E. A.; Kannan, R.; Kleinberg, J.; Papadimitriou, C.; Raghavan, P.; Schöning, U., Theor. Comput. Sci., 289, 69 (2002) · Zbl 1061.68071 · doi:10.1016/s0304-3975(01)00174-8
[14] Schöning, T., 410-414 (1999), IEEE
[15] Buhrman, H.; Tromp, J.; Vitányi, P.; Orejas, F.; Spirakis, P. G.; van Leeuwen, J., Automata, Languages and Programming, 1017-1027 (2001), Springer Berlin Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg
[16] Note that the binary representation without leading zeros of a positive integer y has ⌈log_2(y + 1)⌉ bits.
[17] Note that in the supplemental material of Ref. 1, Convert_N was called Append_0.
[18] The result can be generalized to the traveling salesman problem, subject to constraints on the distances depending on the number of available qubits.
[19] For simplicity of notation, we will in this section not distinguish between an edge e and its number in the enumeration, and simply write e = 10 to mean that e is the 10th edge according to the enumeration. We do the same for vertices.
[20] Brassard, G.; Høyer, P.; Mosca, M.; Tapp, A., Quantum Computation and Information (2002), AMS
[21] Yoder, T. J.; Low, G. H.; Chuang, I. L., Phys. Rev. Lett., 113, 210501 (2014) · doi:10.1103/physrevlett.113.210501
[22] Reingold, O., 376-385 (2005), ACM: ACM, New York, NY, USA
[23] Lange, K.-J.; McKenzie, P.; Tapp, A., J. Comput. Syst. Sci., 60, 354 (2000) · Zbl 0956.68057 · doi:10.1006/jcss.1999.1672
[24] Williams, R., Space-efficient reversible simulations, Technical Report (2000)
[28] Lloyd, S., Science, 273, 1073 (1996) · Zbl 1226.81059 · doi:10.1126/science.273.5278.1073
[29] Wecker, D.; Hastings, M. B.; Troyer, M., Phys. Rev. A, 92, 042303 (2015) · doi:10.1103/physreva.92.042303
[30] Yung, M.-H.; Whitfield, J. D.; Boixo, S.; Tempel, D. G.; Aspuru-Guzik, A., Introduction to quantum algorithms for physics and chemistry, Quantum Information and Computation for Chemistry, 67-106 (2014), John Wiley & Sons, Inc. · Zbl 1371.68091
[31] Ge, Y.; Tura, J.; Cirac, J. I., J. Math. Phys., 60, 022202 (2019) · Zbl 1409.81028 · doi:10.1063/1.5027484
[32] Iwama, K.; Nakashima, T., 108-117 (2007), Springer-Verlag: Springer-Verlag, Berlin, Heidelberg
[33] Xiao, M.; Nagamochi, H., Algorithmica, 74, 713 (2016) · Zbl 1348.90559 · doi:10.1007/s00453-015-9970-4
[34] Cygan, M.; Nederlof, J.; Pilipczuk, M.; Pilipczuk, M.; van Rooij, J. M. M.; Wojtaszczyk, J. O., 150-159 (2011), IEEE
[35] Montanaro, A., Theory Comput., 14, 1 (2018) · Zbl 1417.68046 · doi:10.4086/toc.2018.v014a015
[36] Ambainis, A.; Kokainis, M., 989-1002 (2017), ACM: ACM, New York, NY, USA
[37] The value of f(c) depends on the constants A and B defined in Example 1. Straightforwardly encoding each trit using two qubits yields A ≈ 39 and B ≈ 137 for the FCHC quantum algorithm in Theorem 3. These values can likely be improved significantly.
[38] Campbell, E.; Khurana, A.; Montanaro, A., Applying quantum algorithms to constraint satisfaction problems, Quantum, 3, 167 (2019) · doi:10.22331/q-2019-07-18-167
[39] Preskill, J., Quantum, 2, 79 (2018) · doi:10.22331/q-2018-08-06-79
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.