arXiv:2002.02242 · International Journal of Geometric Methods in Modern Physics

Transition probabilities in generalized quantum search Hamiltonian evolutions

Steven Gassner, Carlo Cafaro, Salvatore Capozzıello

Published Nov 12, 2019• 8 citations

Abstract

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.

DOI: 10.1142/s0219887820500061

Related papers

Singularity of Farhi–Gutmann Analog Quantum Search

Luo Shun-Long, Zhengmin Zhang

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.

Communications in Theoretical PhysicsMay 15, 20041 citation

Singularity of Farhi-Gutmann Analog Quantum Search

LUOShun-Long, ZHANGZheng-Min

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 thetarget state is strictly less than 1 over the entire evolution period, and the first time to achieve this maximum fidelity is of order √n/√1+cN, whose behavior depends crucially on whether c = 0 or not (here N is the total number of items, and the original Farhi-Gutmann case corresponds to c = 0). Moreover, when c ≠ 0 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.

理论物理通讯：英文版Jan 1, 20040 citations

Continuous-time quantum search and time-dependent two-level quantum systems

Carlo Cafaro, Paul M. Alsing

It was recently emphasized by Byrnes, Forster and Tessler [Phys. Rev. Lett. 120 (2018) 060501] that the continuous-time formulation of Grover’s quantum search algorithm can be intuitively understood in terms of Rabi oscillations between the source and the target subspaces. In this work, motivated by this insightful remark and starting from the consideration of a time-independent generalized quantum search Hamiltonian as originally introduced by Bae and Kwon [Phys. Rev. A 66 (2002) 012314], we present a detailed investigation concerning the physical connection between quantum search Hamiltonians and exactly solvable time-dependent two-level quantum systems. Specifically, we compute in an exact analytical manner the transition probabilities from a source state to a target state in a number of physical scenarios specified by a spin-[Formula: see text] particle immersed in an external time-dependent magnetic field. In particular, we analyze both the periodic oscillatory as well as the monotonic temporal behaviors of such transition probabilities and, moreover, explore their analogy with characteristic features of Grover-like and fixed-point quantum search algorithms, respectively. Finally, we discuss from a physics standpoint the connection between the schedule of a search algorithm, in both adiabatic and nonadiabatic quantum mechanical evolutions, and the control fields in a time-dependent driving Hamiltonian.

arXiv:1903.11188International Journal of Quantum InformationApr 1, 201923 citations

A quantum partial adiabatic evolution and its application to quantum search problem

Jie Sun, Hui Zheng, Songfeng Lu

This paper presents a framework for quantum partial adiabatic evolution and applies it to re-examine the well-known quantum search problem. We particularly focus on a detailed analysis of the algorithm’s success probability, which serves as a clear criterion for differentiating valid implementations from invalid ones. Specifically, when the time complexity aligns with the optimal quantum computation, the algorithm achieves a substantially high success probability. Conversely, so-called “improved” versions that exceed the quadratic speedup characteristic of quantum computing exhibit a negligibly low success probability with the increase of target elements. These findings underscore the critical importance of selecting the appropriate evolution interval and the correct method for calculating the success probability in studies of quantum partial adiabatic evolution.

Frontiers in PhysicsJan 8, 20262 citations

Continuous-time Quantum Algorithms: Searching and Adiabatic Computation

Lawrence M. Ioannou

One of the most important quantum algorithms is Grover's search algorithm [G96]. Quantum searching can be used to speed up the search for solutions to NP-complete problems e. g. 3SAT. Even so, the best known quantum algorithms for 3SAT are considered inefficient. \nSoon after Grover's discovery, Farhi and Gutmann [FG96] devised a "continuous-time analogue" of quantum searching. More recently Farhi et. al. [FGGS00] proposed a continuous-time 3SAT algorithm which invokes the adiabatic approximation [M76]. Their algorithm is difficult to analyze, hence we do not know whether it can solve typical 3SAT instances faster than Grover's search algorithm can. \nI begin with a review of the discrete- and continuous-time models of quantum computation. I then make precise the notion of "efficient quantum algorithms", motivating sufficient conditions for discrete- and continuous-time algorithms to be considered efficient via discussion of standard techniques for discrete-time simulation of continuous-time algorithms. After reviewing three quantum search algorithms [F00,FG96,G96], I develop the adiabatic 3SAT algorithm as a natural extension of Farhi and Gutmann's search algorithm. Along the way, I present the adiabatic search algorithm [vDMV01] and remark on its discrete-time simulation. Finally I devise a generalization of the adiabatic algorithm and prove some lower bounds for various cases of this general framework. \nUPDATE (February 2003): Please see article http://arxiv. org/abs/quant-ph/0302138 for a resolution to the problem of simulating the continuous-time adiabatic search algorithm with a quantum circuit using only O(sqrt(N)) resources.

Jan 1, 20024 citations

Symmetry-Based Perspectives on Hamiltonian Quantum Search Algorithms and Schrodinger's Dynamics between Orthogonal States

Carlo Cafaro, James Schneeloch

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.

quant-pharXiv:2601.10655Jan 16, 20260 citations