Quantum Adiabatic Evolution with a Special Kind of Interpolating Paths
We study a special kind of interpolating paths in quantum adiabatic search algorithms. With this special kind of adiabatic paths, notably we find that even when the parameter n within it tends to infinity, the adiabatic evolution would be a failure if the
- PDF / 188,239 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 26 Downloads / 183 Views
2 3
1 School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074, China [email protected] Shenzhen Research Institute, Huazhong University of Science and Technology, Shenzhen 518063, China Department of Information Technology, Vaasa University of Applied Sciences, Vaasa, Finland
Abstract. We study a special kind of interpolating paths in quantum adiabatic search algorithms. With this special kind of adiabatic paths, notably we find that even when the parameter n within it tends to infinity, the adiabatic evolution would be a failure if the initial state is orthogonal to the final target state. But superficially, it seems that the minimum gap of the quantum system happening at the end of the computation would not affect the validity of the algorithm, since each ground state of the problem Hamiltonian encodes a solution to the problem. When the beginning state has a nonzero overlap with the final state, again if the parameter n within the special interpolating paths tends to infinity, it may give ones the counterintuitive impression that the adiabatic evolution could be considerably faster than the usual simple models of adiabatic evolution, even possible with constant time complexity. However, the fact is that as in the usual case, the quadratic speedup is the quantum algorithmic performance limit for which this kind of interpolating functions can provide for the adiabatic evolution. We also expose other easily made mistakes which may lead to draw the wrong conclusions about the validity of the adiabatic search algorithms. Keywords: Quantum computing Interpolating paths
1
· Adiabatic evolution
Introduction
Quantum computing has attracted a great deal of attention in recent years. Quantum algorithms can solve certain problems significantly faster than the known classical algorithms [1–4]. When the algorithms, mentioned above were invented, they were implemented on the quantum circuits, which involves a sequence of unitary operators. So we can say these algorithms stay within the traditional paradigm of c Springer Nature Switzerland AG 2019 K. Arai et al. (Eds.): FICC 2018, AISC 887, pp. 718–723, 2019. https://doi.org/10.1007/978-3-030-03405-4_51
Quantum Adiabatic Evolution with a Special Kind of Interpolating Paths
719
quantum computing. In the year around 2000, another novel paradigm based on adiabatic evolution was proposed by Farhi et al. for quantum computation [5]. Quantum adiabatic computing has also attracted lots of interests by more and more researchers. For example, the adiabatic evolution based quantum algorithms are widely used for solving various types of interesting problems, such as [6–11]. A nature question is that how powerful is this new model of quantum computation compared with the quantum circuit computing? This question was firstly solved by Aharonov et al., who showed that adiabatic evolution is polynomially equivalent to the standard model of quantum computation [12]. Later, a simplified proof between these two models has also appeared [13]. F
Data Loading...
