Abstract We analyze the possibility of modifying the original Farhi–Gutmann Hamiltonian algorithm in order to speed up the procedure for producing a suitably distributed unknown normalized quantum mechanical state. Such a modification is feasible provided only a nearly optimal fidelity is sought. We propose to select the lower bounds of the nearly optimal fidelity values such that their deviations from unit fidelity are less than the minimum error probability characterizing the optimum ambiguous discrimination scheme between the two non-orthogonal quantum states yielding the chosen nearly optimal fidelity values. Departing from the working assumptions of perfect state overlap and uniform distribution of the target state on the unit sphere in N -dimensional complex Hilbert space, we determine that the modified algorithm can indeed outperform the original analog counterpart of a quantum search algorithm. This performance enhancement occurs in terms of speed for a convenient choice of both the ratio γ = E ′ / E between the energy eigenvalues E ′ and E of the modified search Hamiltonian and the quantum mechanical overlap x between the source and the target states. Finally, we briefly discuss possible analytical improvements of our investigation together with its potential relevance in practical quantum engineering applications.
Abstract We analyze the possibility of modifying the original Farhi–Gutmann Hamiltonian algorithm in order to speed up the procedure for producing a suitably distributed unknown normalized quantum mechanical state. Such a modification is feasible provided only a nearly optimal fidelity is sought. We propose to select the lower bounds of the nearly optimal fidelity values such that their deviations from unit fidelity are less than the minimum error probability characterizing the optimum ambiguous discrimination scheme between the two non-orthogonal quantum states yielding the chosen nearly optimal fidelity values. Departing from the working assumptions of perfect state overlap and uniform distribution of the target state on the unit sphere in N -dimensional complex Hilbert space, we determine that the modified algorithm can indeed outperform the original analog counterpart of a quantum search algorithm. This performance enhancement occurs in terms of speed for a convenient choice of both the ratio γ = E ′ / E between the energy eigenvalues E ′ and E of the modified search Hamiltonian and the quantum mechanical overlap x between the source and the target states. Finally, we briefly discuss possible analytical improvements of our investigation together with its potential relevance in practical quantum engineering applications.
A relevant problem in quantum computing concerns how fast a source state can be driven into a target state according to Schrödinger’s quantum mechanical evolution specified by a suitable driving Hamiltonian. In this paper, we study in detail the computational aspects necessary to calculate the transition probability from a source state to a target state in a continuous time quantum search problem defined by a multiparameter generalized time-independent Hamiltonian. In particular, quantifying the performance of a quantum search in terms of speed (minimum search time) and fidelity (maximum success probability), we consider a variety of special cases that emerge from the generalized Hamiltonian. In the context of optimal quantum search, we find it is possible to outperform, in terms of minimum search time, the well-known Farhi–Gutmann analog quantum search algorithm. In the context of nearly optimal quantum search, instead, we show it is possible to identify sub-optimal search algorithms capable of outperforming optimal search algorithms if only a sufficiently high success probability is sought. Finally, we briefly discuss the relevance of a tradeoff between speed and fidelity with emphasis on issues of both theoretical and practical importance to quantum information processing.
We show that the Farhi–Gutmann analog quantum search is a singular algorithm in the following sense: when the original driving Hamiltonian is perturbed slightly such that it is made of projections to the starting state and to the target state with different energies, the maximum fidelity (transition probability) between the searching state and the target state is strictly less than 1 over the entire evolution period, and the first time to achieve this maximum fidelity is of order , whose behavior depends crucially on whether or not (here N is the total number of items, and the original Farhi–Gutmann case corresponds to ). Moreover, when and N tends to infinity, the maximum fidelity tends to zero, and the first time to achieve the maximum fidelity tends to a positive constant! The condition for guaranteeing the algorithm's efficiency is determined explicitly.
It is known that the continuous-time variant of Grover's search algorithm is characterized by quantum search frameworks that are governed by stationary Hamiltonians, which result in search trajectories confined to the two-dimensional subspace of the complete Hilbert space formed by the source and target states. Specifically, the search approach is ineffective when the source and target states are orthogonal. In this paper, we employ normalization, orthogonality, and energy limitations to demonstrate that it is unfeasible to breach time-optimality between orthogonal states with constant Hamiltonians when the evolution is limited to the two-dimensional space spanned by the initial and final states. Deviations from time-optimality for unitary evolutions between orthogonal states can only occur with time-dependent Hamiltonian evolutions or, alternatively, with constant Hamiltonian evolutions in higher-dimensional subspaces of the entire Hilbert space. Ultimately, we employ our quantitative analysis to provide meaningful insights regarding the relationship between time-optimal evolutions and analog quantum search methods. We determine that the challenge of transitioning between orthogonal states with a constant Hamiltonian in a sub-optimal time is closely linked to the shortcomings of analog quantum search when the source and target states are orthogonal and not interconnected by the search Hamiltonian. In both scenarios, the fundamental cause of the failure lies in the existence of an inherent symmetry within the system.
We use geometric concepts originally proposed by Anandan and Aharonov [Phys. Rev. Lett. 65, 1697 (1990)] to show that the Farhi-Gutmann time-optimal analog quantum search evolution between two orthogonal quantum states is characterized by unit efficiency dynamical trajectories traced on a projective Hilbert space. In particular, we prove that these optimal dynamical trajectories are the shortest geodesic paths joining the initial and the final states of the quantum evolution. In addition, we verify they describe minimum uncertainty evolutions specified by an uncertainty inequality that is tighter than the ordinary time-energy uncertainty relation. We also study the effects of deviations from the time-optimality condition from our proposed Riemannian geometric perspective. Furthermore, after pointing out some physically intuitive aspects offered by our geometric approach to quantum searching, we mention some practically relevant physical insights that could emerge from the application of our geometric analysis to more realistic time-dependent quantum search evolutions. Finally, we briefly discuss possible extensions of our paper to the geometric analysis of the efficiency of thermal trajectories of relevance in quantum computing tasks.
The Analysis on the Running Time of the Generalized Quantum Search Hamiltonian : O(N1/4) and O(1) Time Resources
Farhi et al. suggested the analogue quantum search Hamiltonian and Fenner also proposed the intuitive quantum search Hamiltonian. Recently the generalized quantum search Hamiltonian containning hamiltonians of Farhi et al. and Fenner was presented in quant-ph/0110020. In this letter, we analyze the running time of the generalized quantum search Hamiltonian. Our analysis displays two surprising results. The first is the exponential speedup(T = O(N 1/4)), and the next O(1) time resource. In 1996, Farhi et al. suggested the analogue quantum search algorithm based on Hamiltonian evolution.[1] The Hamiltonian to solve the search problem is Haf = Ed(|w〉〈w|+|ψ〉〈ψ|). In the Hamiltonian Haf, |w 〉 is the target state that we have to find, |ψ 〉 is the initial state that is a superposition of N states, E is a constant in unit of energy, and d is a constant. Fenner [2] also proposed the quantum search Hamiltonian Hif = −2iEx(|w〉〈ψ | − |ψ〉〈w|), where x = 〈w|ψ 〉 ≈ 1 √. The Hamiltonian Hif is called the intuitive quantum search Hamil-N tonian. Recently, the generalized quantum search Hamiltonian including hamiltonians of Farhi et al. and Fenner was presented.[3] The Hamiltonian is as follows: Hyj = E[d(|w〉〈w | + |ψ〉〈ψ|) + r(e iφ |w〉〈ψ | + e −iφ |ψ〉〈w|)] (1) where, r is a constant, and φ is a phase. The initial state can be written as |ψ 〉 = x|w 〉 + √ 1 − x 2 |β〉, where |β 〉 is the orthogonal complement of the state |w〉. If the phase is given by φ = nπ(n is an integer), then the Hamiltonian finds the target state with probability one, but if not, the probability to find the target becomes 1 − O(x 2) ≈ 1 − O(1/N).
We study a variant of the quantum approximate optimization algorithm [E. Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028] with a slightly different parametrization and a different objective: rather than looking for a state which approximately solves an optimization problem, our goal is to find a quantum algorithm that, given an instance of the maximum 2-satisfiability problem (MAX-2-SAT), will produce a state with high overlap with the optimal state. Using a machine learning approach, we chose a ``training set'' of instances and optimized the parameters to produce a large overlap for the training set. We then tested these optimized parameters on a larger instance set. As a training set, we used a subset of the hard instances studied by Crosson, Farhi, C. Y.-Y. Lin, H.-H. Lin, and P. Shor (CFLLS) (arXiv:1401.7320). When tested, on the full set, the parameters that we find produce a significantly larger overlap than the optimized annealing times of CFLLS. Testing on other random instances from 20 to 28 bits continues to show improvement over annealing, with the improvement being most notable on the hardest instances. Further tests on instances of MAX-3-SAT also showed improvement on the hardest instances. This algorithm may be a possible application for near-term quantum computers with limited coherence times.