Search

In this paper, we further verify the validity of the quantum partial adiabatic search algorithm which was initialized in the previous related works by revisiting its quantum circuit model. The main results got here are as follows. When considering implementing quantum partial adiabatic evolution on a quantum circuit, a correction is given for the time slice estimation for the first stage during this approximation in the previous related works, new evidence is provided for a time complexity cost O (N / M) of quantum partial adiabatic algorithm is impossible, and the correct time complexity O (N / M) of it is emphasized once more according to its circuit correspondence, in which N is the total number of elements in the search problem of which M of them are the marked ones. The findings exposed are hopeful for revisiting quantum partial adiabatic evolution and its connection with the quantum circuit model. [ABSTRACT FROM AUTHOR]

Recently, Kieu derived a new class of time–energy uncertainty relations, which is not only formal but also suitable for evaluating the speed limit of quantum dynamics. However, when this time–energy uncertainty relation was applied to study the quantum adiabatic Grover's search, some approximation had been done for reaching the right conclusion. That is, the final state being orthogonal to the initial state in this problem was assumed which may cause confusion, while the truth is that the overlap between these two states is indeed very small when the problem size is very big but not equal to zero exactly. In this paper, we modify the time–energy uncertainty relation of Kieu applied to two quantum evolutions of Grover's problem, and find that the resulting computational complexities match well with the previous works on this topic but without the need of making the assumption like that in the work of Kieu. [ABSTRACT FROM AUTHOR]

In this paper [J. Sun, S. Lu and F. Liu, Open Syst. Info. Dyn.23(3) (2016) 1650016], we have studied a general class of adiabatic evolutions in quantum adiabatic search type problem, and found another limitation on it, besides those reported in our early work. In this paper, we extend this study by considering adding an extra driving scheme to the system Hamiltonian of this type of quantum adiabatic evolution. It will be shown that, like the previous study in [J. Sun, S. Lu and F. Liu, Open Syst. Info. Dyn.23(3) (2016) 1650016], the limitation above can also possibly penetrate into the search type quantum-adiabatic computation even by this more general family of system Hamiltonian, which may shed light on what we should have in mind when solving practical problems by means of quantum adiabatic evolution. [ABSTRACT FROM AUTHOR]

It is known that when the initial state has no overlap with the final state in an adiabatic computation, an extra assisted driving Hamiltonian has to be used to avoid the failure of quantum adiabatic algorithm. This assisted Hamiltonian has a relatively fixed form, which can be seen in the related literature but the mechanism behind it is still not clear enough. In this paper, we discuss the usefulness of a generalized form of assisted driving Hamiltonian in adiabatic evolution which may shed light on this problem. [ABSTRACT FROM AUTHOR]

The general class of models of adiabatic evolution was proposed to speed up the usual adiabatic computation in the case of quantum search problem. It was shown [8] that, by temporarily increasing the ground state energy of a time-dependent Hamiltonian to a suitable quantity, the quantum computation can perform the calculation in time complexity O(1). But it is also known that if the overlap between the initial and final states of the system is zero, then the computation based on the generalized models of adiabatic evolution can break down completely. In this paper, we find another severe limitation for this class of adiabatic evolution-based algorithms, which should be taken into account in applications. That is, it is still possible that this kind of evolution designed to deal with the quantum search problem fails completely if the interpolating paths in the system Hamiltonian are chosen inappropriately, while the usual adiabatic evolutions can do the same job relatively effectively. This implies that it is not always recommendable to use nonlinear paths in adiabatic computation. On the contrary, the usual simple adiabatic evolution may be sufficient for effective use. [ABSTRACT FROM AUTHOR]

In this paper, we propose a modified construction of the quantum adiabatic algorithm for Boolean functions studied by M. Andrecut et al. [13, 14]. Our algorithm has the time complexity for the evaluation of Boolean functions, without additional computational cost of implementing the driving Hamiltonian, which is required by the adiabatic evolution described in [13, 14]. [ABSTRACT FROM AUTHOR]

We study the quantum version of a decision tree classifier to fill the gap between quantum computation and machine learning. The quantum entropy impurity criterion which is used to determine which node should be split is presented in the paper. By using the quantum fidelity measure between two quantum states, we cluster the training data into subclasses so that the quantum decision tree can manipulate quantum states. We also propose algorithms constructing the quantum decision tree and searching for a target class over the tree for a new quantum object. [ABSTRACT FROM AUTHOR]

In this paper, we again discuss quantum search by partial adiabatic evolution, which was first proposed by Zhang et al. In contrast to previous conclusions, we show that partial adiabatic search does not improve the time complexity of a local adiabatic algorithm. Firstly, we show a variant of this algorithm and find that it is equivalent to the original partial adiabatic algorithm, in the sense of the same time complexity. But we give two alternate viewpoints on this 'new' adiabatic algorithm-'global' adiabatic evolution and local adiabatic evolution approaches, respectively. Then, we discuss how global and local adiabatic quantum search can be recast in the framework of partial adiabatic search algorithm. It is found here that the former two algorithms could be considered as special cases of the later one when appropriately tuning the evolution interval of it. Also this implies the flexibility of quantum search based on partial adiabatic evolution. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem that when quantum adiabatic evolution with the most general form of system Hamiltonian will get failed. Here the most general form means that the initial and final Hamiltonians are just designed according to the adiabatic theorem in quantum mechanics. As we will see, even in this most general model of quantum adiabatic evolution, it still exists the possibility that the quantum adiabatic computation can fail totally if some condition is satisfied, which implies the time complexity of the quantum algorithm is infinity. That is, here we propose a rather general criterion for judging whether a quantum adiabatic evolution is successful. This result largely extends the authors' previous research on this topic, and it may be seen as a further important clue for us when designing quantum algorithms in the framework of adiabatic evolution for some practical problems. [ABSTRACT FROM AUTHOR]