Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

理论物理通讯：英文版

Singularity of Farhi-Gutmann Analog Quantum Search

LUOShun-Long, ZHANGZheng-Min

Published Jan 1, 2004• 0 citations
OpenAlex

Abstract

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.

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 Physics•May 15, 2004•1 citation

Transition probabilities in generalized quantum search Hamiltonian evolutions

Steven Gassner, Carlo Cafaro, Salvatore Capozzıello

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.

arXiv:2002.02242•International Journal of Geometric Methods in Modern Physics•Nov 12, 2019•8 citations

Theoretical analysis of a nearly optimal analog quantum search

Carlo Cafaro, Paul M Alsing

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.

arXiv:1903.11186•Physica Scripta•Jun 4, 2019•10 citations

Driving Hamiltonian in a Quantum Search Problem

Kazuto Oshima

We examine the driving Hamiltonian in the analog analogue of Grover's algorithm by Farhi and Gutmann. For a quantum system with a given Hamiltonian $E|w> < w|$, we explicitly show that while the driving Hamiltonian $E|s> < s|$ optimally produces the state $|w>$ from an initial state $|s>$, the driving Hamiltonian $E^{\prime}|s> < s|(E^{\prime} \ne E)$ does not provide any speedup compared even with a classical computation.

arXiv:quant-ph/0111021•Nov 4, 2001•1 citation

An intuitive Hamiltonian for quantum search

Stephen Fenner

We present new intuition behind Grover's quantum search algorithm by means of a Hamiltonian. Given a black-box Boolean function f mapping strings of length n into {0,1} such that f(w) = 1 for exactly one string w, L. K. Grover describes a quantum algorithm that finds w in O(2^{n/2}) time. Farhi & Gutmann show that w can also be found in the same amount time by letting the quantum system evolve according to a simple Hamiltonian depending only on f. Their system evolves along a path far from that taken by Grover's original algorithm, however. The current paper presents an equally simple Hamiltonian matching Grover's algorithm step for step. The new Hamiltonian is similar in appearance from that of Farhi & Gutmann, but has some important differences, and provides new intuition for Grover's algorithm itself. This intuition both contrasts with and supplements other explanations of Grover's algorithm as a rotation in two dimensions, and suggests that the Hamiltonian-based approach to quantum algorithms can provide a useful heuristic for discovering new quantum algorithms.

arXiv:quant-ph/0004091•Apr 24, 2000•7 citations

The Analysis on the Running Time of the Generalized Quantum Search Hamiltonian : $O(N^{1/4})$ and O(1) Time Resources

Joonwoo Bae, Younghun Kwon

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).

•Apr 16, 2002•0 citations
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.
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.
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.
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.
We examine the driving Hamiltonian in the analog analogue of Grover's algorithm by Farhi and Gutmann. For a quantum system with a given Hamiltonian E∣w><w∣E|w> < w|E∣w><w∣, we explicitly show that while the driving Hamiltonian E∣s><s∣E|s> < s|E∣s><s∣ optimally produces the state ∣w>|w>∣w> from an initial state ∣s>|s>∣s>, the driving Hamiltonian E′∣s><s∣(E′≠E)E^{\prime}|s> < s|(E^{\prime} \ne E)E′∣s><s∣(E′=E) does not provide any speedup compared even with a classical computation.
We present new intuition behind Grover's quantum search algorithm by means of a Hamiltonian. Given a black-box Boolean function f mapping strings of length n into {0,1} such that f(w) = 1 for exactly one string w, L. K. Grover describes a quantum algorithm that finds w in O(2^{n/2}) time. Farhi & Gutmann show that w can also be found in the same amount time by letting the quantum system evolve according to a simple Hamiltonian depending only on f. Their system evolves along a path far from that taken by Grover's original algorithm, however. The current paper presents an equally simple Hamiltonian matching Grover's algorithm step for step. The new Hamiltonian is similar in appearance from that of Farhi & Gutmann, but has some important differences, and provides new intuition for Grover's algorithm itself. This intuition both contrasts with and supplements other explanations of Grover's algorithm as a rotation in two dimensions, and suggests that the Hamiltonian-based approach to quantum algorithms can provide a useful heuristic for discovering new quantum algorithms.
The Analysis on the Running Time of the Generalized Quantum Search Hamiltonian : O(N1/4)O(N^{1/4})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).