A fast quantum mechanical algorithm for database search
Open accessAbstract
An unsorted database contains N records, of which just one satisfies a particular property.The problem is to identify that one record.Any classical algorithm, deterministic or probabilistic, will clearly take O (N) steps since on the average it will have to examine a large fraction of the N records.Quantum mechanical systems can do several operations simultaneously due to their wave like properties.This paper gives an O ( JN) step quantum mechanical algorithm for identifying that record.It is within a constant factor of the fastest possible quantum mechanical algorithm.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
0 of 8 cited sources checked · 0 supported · 0 flagged
- Findingnone given
The paper gives an O(√N) step quantum mechanical algorithm for identifying the unique record satisfying a particular property in an unsorted database of N records.
“This paper gives an O ( JN) step quantum mechanical algorithm for identifying that record.”
Quote in the paperSubstantial claim- The authors state this as an assumption: There is a unique state that satisfies the condition C(S)=1.
- The authors state this as an assumption: For any state S, the condition C(S) can be evaluated in unit time.
- Findingreasoning
After applying the diffusion transform to a state with one amplitude k and N-1 amplitudes l, if k is negative and l positive with |k| < l/√N, then both resulting amplitudes are positive.
“Corollary 3.1-Let the state vector be as followsfor any one state the amplitude is k, for each of the remaining (N-1) states the amplitude is 1.Let k and 1 be real numbers (in general the amplitudes can be complex).Let k be negative and 1 be positive such that ~< ~N.Then after applying the diffusion transform both k and 1are positive numbers.”
Quote in the paperSubstantial claim - Findingreasoning
The system is a valid quantum mechanical system.
“First, it is proved that the system is a valid quantum mechanical system (theorems 1 & 2)”
Quote in the paperSubstantial claim - Findingnone given
The algorithm does not use any knowledge about the problem.
“As mentioned in the introduction, the algorithm of this paper does not use any Imowledge about the problem.”
Quote in the paperSubstantial claim - Findingnone given
The diffusion transform D is unitary.
“Theorem 1-The matix D is unitary.”
Quote in the paperSubstantial claim
- Findingreasoning
The algorithm converges to the desired state with probability O(1).
“The following sections prove that the system discussed in section 3 is indeed a valid quantum mechanical system and that it converges to the desired state with a probability O(l).”
Quote in the paperSubstantial claim- The authors state this as an assumption: There is a unique state that satisfies the condition C(S)=1.
- The authors state this as an assumption: For any state S, the condition C(S) can be evaluated in unit time.
- Findingreasoning
D can be expressed as D = FRF, where F is the Fourier transform matrix and R is the rotation matrix.
“Theorem 2 -D can be expressed as D = FRF, where F, the Fourier Transform Matrix and R, the rotation matrix are defined as follows”
Quote in the paperSubstantial claim - Findingreasoning
When k = 1/√2, the probability of the system being in the desired state is 1/2.
“Since the proba-& bility of the system being found in any particular state is proportional to the square of the amplitude, it follows that the probability of the system being in tlhe desired state when k is ~, 1 J2 is k2 = ~.”
Quote in the paperSubstantial claim - Findingnone given
In case there is a unique state SV such that C(SV)=1, the final state is SV with probability at least 1/2.
“In case there is a unique state SV such that C(SV) = 1, the final state is SV with a probability of at least ~. 2”
Quote in the paperNot a substantial claim- The authors state this as an assumption: There is a unique state that satisfies the condition C(S)=1.
- The authors state this as an assumption: For any state S, the condition C(S) can be evaluated in unit time.
- Findingreasoning
The algorithm can be easily modified to handle multiple states satisfying C(S)=1 and return one of them.
“It can be easily modified to take care of the case when there are multiple states satisfying the condition C(S) = 1 and it is required to return one of these.”
Quote in the paperNot a substantial claim - Findingreasoning
The diffusion transform D can be implemented as a product of three unitary transformations D = FRF, each of F and R is a local transition matrix.
“Using the Fourier transformation matrix as defined in section 3, it can be implemented as a product of three unitary transformations as D = FRF, each of F & R is a local transition matrix.”
Quote in the paperSubstantial claim - Premisereasoning
Any classical algorithm, deterministic or probabilistic, takes O(N) steps on average to identify the record in an unsorted database.
“Any classical algorithm, deterministic or probabilistic, will clearly take O (N) steps since on the average it will have to examine a large fraction of the N records.”
Quote in the paperSubstantial claim - Premisecitation
Any quantum mechanical algorithm needs at least Ω(√N) steps to identify the desired element without information about the structure of the database.
“[BBBV94] show in their paper that in order to identify the desired element, without any information about the structure of the database, a quantum mechanical system will need at least Cl ( ~~steps.”
Quote in the paperSubstantial claim0 of 1 sources checked- cites [BBBV94]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Interpretationcitation
The algorithm is within a constant factor of the fastest possible quantum mechanical algorithm.
“It is within a constant factor of the fastest possible quantum mechanical algorithm.”
- Also stated in: § 1.1 Search Problems in Computer Science · plain
“Since the number of steps required by the algorithm of this paper is O ( fi) , it is within a constant factor of the fastest possible quantum mechanical algorithm.”
Quote in the paperSubstantial claim - Also stated in: § 1.1 Search Problems in Computer Science · plain
- Premisecitation
It is not possible to identify the desired element in fewer than Ω(√N) steps.
“There is a matching lower Ixmnd from the paper [BBBV94] that suggests that it is not possible to identify the desired element in fewer than Q ( ~N) steps.”
Quote in the paperSubstantial claim0 of 1 sources checked- cites [BBBV94]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Interpretationcitation
In order to correctly decide an answer sensitive to N queries, the running time must be T = Ω(√N).
“So in order to correctly decide the answer which is sensitive to N queries will take a running time of T = L2 ( ~N) .”
Quote in the paperSubstantial claim - Interpretationreasoning
The algorithm is significantly faster than any classical algorithm can be.
“This paper applies quantum computing to a mundane problem in information processing and presents an algorithm that is significantly faster than any classical algorithm can be.”
Quote in the paperSubstantial claim - Interpretationnone given
Once an experiment with finite success probability ε is designed, in O(1/ε) repetitions the probability of success can be made very close to unity.
“Finally it is proved that once we can design an experiment with a finite success probability of () E, in O ~repetitions of the experiment it is possible to have a probability of success very close to unity.”
Quote in the paperNot a substantial claim - Premisecitation
In order to conserve probabilities, the state transition matrix has to be unitary.
“It can be shown that in order to conserve probabilities, the state transition matrix has to be unitary [BV93].”
Quote in the paperSubstantial claim0 of 1 sources checked- cites [BV93]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Premisecitation
Any quantum mechanical algorithm running for T steps is only sensitive to O(T^2) queries.
“This result states that any quantum mechanical algorithm running for T steps is cmly sensitive to O ( T2) queries (i.e. if there are more possible queries, then the answer to at least one can be flipped without affecting the behavior of the algorithm).”
Quote in the paperSubstantial claim0 of 1 sources checked- cites [BBBV94]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Classified as probably not a substantial claim. 8
- May combine two claims. 4
- The quote only partly states this claim. 1
Probably not a substantial claim: may not pass S3 (load-bearing).
Findingnone givenIf an experiment with success probability ε is repeated K times, the probability that the outcome does not happen even once is ≤ e^{-K}.
“Theorem 5-Let the probability of a particular outcome in an experiment be &.Then if the experiment be repeated ~times, the probability that the outcome does not happen even once is less than or equal to e-K.”
Quote in the paperNot a substantial claimMay combine two claims.
FindingreasoningAfter steps (a) and (b) of the algorithm, the change in k is lower bounded by a positive amount, and l remains positive.
“The change in k ( Ak) after steps (a) and (b) of the algorithm is lower bounded by Ak>~.Also after steps (a) and (b), 1>0.2fi”
Quote in the paperSubstantial claimThe quote only partly states this claim.
FindingreasoningThere exists M less than √N such that in M repetitions of the loop, k becomes 1/√2.
“Using this it immediately follows that there exists a number M less than EN, such that in M repetitions of the loop in step (ii), k wifl become ~.”
Quote in the paperSubstantial claimMay combine two claims.
PremisereasoningThe most efficient classical algorithm for unsorted database search examines items one by one and needs to look at an average of N/2 items before finding the desired one.
“The most efficient classical algorithm for this is to examine the items in the database one by one.”
Quote in the paperSubstantial claimProbably not a substantial claim: may not pass S3 (load-bearing).
PremisecitationVery recent results have shown the existence of quantum mechanical error correcting codes which enable transmission of data even in the presence of noise.
“Very recent results [Shor95] have shown the existence of quantum mechanical error corr~ting cod~which enable transmission of data even in the presence of noise”
Quote in the paperNot a substantial claim0 of 1 sources checked- cites [Shor95]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
Probably not a substantial claim: may not pass S3 (load-bearing).
Premisenone givenShor's algorithm is the only known algorithm that solves the problem in O(log N) steps.
“This algorithm, by cleverly making use of some features of the structure of the problem, is the only known algorithm that solves the problem in O (logIV) steps.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S3 (load-bearing).
Premisenone givenThe phase of the amplitude does not have an analog in classical probabilistic algorithms.
“The phase does not have an analog in classical probabilistic algorithms.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.
PremisereasoningIn quantum mechanics, the complete description of the system requires the amplitudes over all states; probabilities alone are not enough.
“This illustrates the point that, in quantum mechanics, the complete description of the system requires the amplitudes over all states, just the probabilities is not enough.”
Quote in the paperNot a substantial claimProbably not a substantial claim: may not pass S3 (load-bearing).
PremisecitationShor's primality testing algorithm for a number N can be viewed as a search of the (N-1) numbers smaller than N to see if any is a factor of N.
“For example Shor's primality testing algorithm [Shor94] for a number N can be viewed as a search of the (N-l) numbers smaller than N to see if any of them is a factor of N.”
Quote in the paperNot a substantial claim0 of 1 sources checked- cites [Shor94]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
Probably not a substantial claim: may not pass S3 (load-bearing).
PremisecitationThere is a scheme by which it is possible to modify any algorithm that solves an NP-search problem with a unique solution and use it to solve an NP-search problem in general.
“There is also a scheme discussed in [VV86] by which it is possible to modify any algorithm that solves an NPsearch problem with a unique solution and use it to solve an NP-search problem in general.”
Quote in the paperNot a substantial claim0 of 1 sources checked- cites [VV86]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
Probably not a substantial claim: may not pass S3 (load-bearing). May combine two claims.
PremisecitationThe Fourier transformation operation is one of the things that makes quantum mechanical algorithms more powerful than classical algorithms and forms the basis for most significant quantum mechanical algorithms.
“This operation is one of the things that makes quantum mechanical algorithms more powerful than classical algorithms and forms the basis for most significant quantum mechanical algorithms.”
Quote in the paperNot a substantial claim0 of 1 sources checked- cites [DJ92]
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
The authors state this as an assumption.
There is a unique state that satisfies the condition C(S)=1.
“Let there be a unique state, say Sv, that satisfies the condition C(SV) = 1, whereas for all other states S, C(S) = 0”
“The algorithm as discussed here assumes a unique state that satisfies the desired condition.”
The authors state this as an assumption.
For any state S, the condition C(S) can be evaluated in unit time.
“(assume that for any state S, the condition C(S) can be evaluated in unit time)”
The paper relies on this without support.
There does not exist any sorting on the database that would aid selection of the desired item.
“However, there does not exist any sorting on the database that would aid its selection.”
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Grover's algorithm offers a quadratic speed-up for brute-force key search, effectively halving the security margin of symmetric ciphers.
“Symmetric cryptography remains comparatively resilient, yet Grover's algorithm offers a quadratic speed-up for brute-force key search, effectively halving the security margin of symmetric ciphers [13].”
From Harvest-Now, Decrypt-Later: A Temporal Cybersecurity Risk in the Quantum Transition (2025) · cites this paper as [13]
The Abstract reports O(N) steps for classical search and an O(√N)-step quantum algorithm, supporting the quadratic speed-up for unstructured search. The paper does not discuss brute-force cipher-key search or assess the security margin of symmetric ciphers; applying its result to those claims goes beyond what this source states. (LLM, conf=0.85)
Experimental — accuracy not yet measuredGrover's algorithm can facilitate a quantum birthday attack to find collisions, thereby necessitating an output of larger size for hash functions.
“Similarly, for hash functions, Grover's algorithm [185] can facilitate quantum birthday attack to find collision, thereby necessitating an output of larger size.”
From Zero Trust Architecture (ZTA): A Comprehensive Survey (2022) · cites this paper as [185]
The Abstract describes Grover’s quantum search algorithm and its square-root speedup for finding a record in an unsorted database. The paper does not discuss hash functions, quantum birthday attacks, collisions, or the need for larger hash outputs, so it does not support the claimed application. (LLM, conf=0.82)
Experimental — accuracy not yet measuredGrover's algorithm gives a quadratic advantage for mining blocks in proof-of-work consensus protocols.
“Similarly, Grover’s algorithm concedes a quadratic advantage for mining blocks in certain consensus protocols such as proof of work.”
From Quantum-resistance in blockchain networks (2023) · cites this paper as [71]
The Abstract (page not listed) reports an O(√N) quantum search algorithm versus O(N) classical search, supporting the quadratic advantage. It does not address block mining or proof-of-work consensus, so the application to those protocols is not established by this paper. (LLM, conf=0.88)
Experimental — accuracy not yet measuredQuantum computers will be able to find proof-of-work nonces quadratically faster using Grover's algorithm.
“Quantum computers will be able to find these nonces quadratically faster using Grover’s algorithm71.”
From Quantum-resistance in blockchain networks (2023) · cites this paper as [71]
The Abstract reports an O(√N) quantum search algorithm versus O(N) classical search, and the discussion on p. 114 says the algorithm can be modified when multiple states satisfy the condition. That supports the claimed quadratic search speedup, but our copy does not address proof-of-work nonces specifically or establish the claim about future computers finding them. (LLM, conf=0.82)
Experimental — accuracy not yet measuredThis HNDL model is realistic given the falling cost of storage, the rise of large-scale surveillance infrastructures, and the expected disruption of quantum algorithms such as Shor's and Grover's.
“This model is realistic given the falling cost of storage, the rise of large-scale surveillance infrastructures, and the expected disruption of quantum algorithms such as Shor's and Grover's [1,2,13].”
From Harvest-Now, Decrypt-Later: A Temporal Cybersecurity Risk in the Quantum Transition (2025) · cites this paper as [13]
The Abstract describes Grover’s quantum search algorithm as taking O(√N) steps where classical search takes O(N), and the Introduction mentions Shor’s efficient factoring algorithm. These passages support the claim that the algorithms offer substantial computational advances, but they do not address their expected disruption of encryption or the realism of the HNDL model. Falling storage costs and surveillance infrastructure are not claims this citation specifically supports. (LLM, conf=0.84)
Experimental — accuracy not yet measured
Grover's algorithm provides only a quadratic speedup, effectively halving brute-force resistance; comparable security margins can be restored by doubling key sizes (e.g., AES-128 to AES-256).
“Grover's algorithm provides only a quadratic speedup, effectively halving brute-force resistance. Comparable security margins can be restored by doubling key sizes (for example, AES-128 to AES-256) [13].”
From Harvest-Now, Decrypt-Later: A Temporal Cybersecurity Risk in the Quantum Transition (2025) · cites this paper as [13]
The Abstract reports O(N) classical search versus an O(√N) quantum algorithm, supporting the quadratic-speedup claim for unstructured search. The paper does not discuss cryptographic keys, security margins, or AES-128 and AES-256; doubling key size is an inference from its search result, not a recommendation the paper makes. (LLM, conf=0.87)
Experimental — accuracy not yet measuredAES-256 maintains post-quantum security margins, whereas AES-128 requires upgrading to maintain equivalent protection levels.
“This explains why AES-256 maintains post-quantum security margins, whereas AES-128 requires upgrading to maintain equivalent protection levels [13,14].”
From Harvest-Now, Decrypt-Later: A Temporal Cybersecurity Risk in the Quantum Transition (2025) · cites this paper as [13]
The Abstract (page not provided) reports a quantum algorithm that searches N possibilities in O(√N) steps, supporting the general rationale for reduced security against exhaustive search. It does not discuss AES-128, AES-256, post-quantum security margins, or whether an upgrade is required, so the specific comparison is not supported by this paper. (LLM, conf=0.78)
Experimental — accuracy not yet measuredGrover's algorithm shows that symmetric cryptography, though more resilient, also demands doubled key sizes to maintain equivalent margins.
“At the same time, Grover's algorithm shows that symmetric cryptography, though more resilient, also demands doubled key sizes to maintain equivalent margins [13].”
From Harvest-Now, Decrypt-Later: A Temporal Cybersecurity Risk in the Quantum Transition (2025) · cites this paper as [13]
The Abstract reports that Grover’s algorithm searches N possibilities in O(√N) steps rather than the classical O(N); the paper’s abstracted problem also describes a search space of 2^n bit strings. That square-root speedup supports the inference about doubling key length for exhaustive search, but the paper does not discuss symmetric cryptography, compare its resilience with other cryptography, or recommend key sizes. (LLM, conf=0.86)
Experimental — accuracy not yet measuredGrover-based optimization algorithms such as Grover Adaptive Search have been proposed.
“In this sense, Grover-based optimization algorithms [184] such as Grover Adaptive Search [161] have been proposed.”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [184]
The Abstract describes Grover’s quantum algorithm for finding a record that satisfies a condition, supporting the reference to the search method underlying “Grover-based” algorithms. It does not describe an optimization algorithm or Grover Adaptive Search; the citing sentence gives a separate citation for that example. (LLM, conf=0.83)
Experimental — accuracy not yet measuredGrover's work shows how to accept the class NP relative to any oracle on a quantum computer in time O(2^{n/2}).
“The former bound is tight since recent work of Grover [13] shows how to accept the class NP relative to any oracle on a quantum computer in time O (2 n/ 2 ).”
From Strengths and Weaknesses of Quantum Computing (1997) · cites this paper as [13]
The Abstract gives an O(√N)-step quantum search algorithm, and §1.1 discusses NP-complete SAT as a search over 2^n assignments; together these support the 2^{n/2} search bound. The paper does not establish the stated bound for the whole class NP relative to any oracle. Its discussion of handling multiple satisfying states (p. 114) also describes a procedure with log N repetitions. (LLM, conf=0.83)
Experimental — accuracy not yet measuredIn view of Grover's algorithm, the constant '1/2' in the statement of Theorem 3.5 cannot be improved.
“In view of Grover's algorithm [13], we know that the constant '1 / 2' in the statement of Theorem 3.5 cannot be improved.”
From Strengths and Weaknesses of Quantum Computing (1997) · cites this paper as [13]
The introduction reports an O(√N)-step search algorithm, and section 6 describes a matching Ω(√N) lower bound. That supports the optimality of the one-half exponent for this search problem, but our copy does not state Theorem 3.5 or establish what its constant ‘1/2’ measures. (LLM, conf=0.75)
Experimental — accuracy not yet measuredThe o(2^{n/2}) lower bound for NP relative to a random oracle is tight.
“The former bound is tight since recent work of Grover [13] shows how to accept the class NP relative to any oracle on a quantum computer in time O (2 n/ 2 ).”
From Strengths and Weaknesses of Quantum Computing (1997) · cites this paper as [13]
The Abstract gives an O(√N) quantum search algorithm, and §1.1 relates a search space of N = 2^n to NP-complete problems. Section 6 (p. 114) describes a matching lower bound for finding a desired item. The copy does not establish the claimed O(2^{n/2}) running time for all of NP relative to any oracle, or state a lower bound for NP relative to a random oracle. (LLM, conf=0.83)
Experimental — accuracy not yet measuredGrover's algorithm offers quadratic speedup over classical searching methods.
“Grover’s algorithm [54] is a quantum algorithm for searching in a database, ofering quadratic speedup over classical searching methods.”
From QASMBench: A Low-Level Quantum Benchmark Suite for NISQ Evaluation and Simulation (2023) · cites this paper as [54]
Quantum machines can recognize L_A quadratically faster, in time O(√2^n), using Grover's algorithm.
“However, quantum machines can recognize this language quadratically faster, in time O ( √ 2 n ), using Grover's algorithm [13].”
From Strengths and Weaknesses of Quantum Computing (1997) · cites this paper as [13]
Grover's result gives a black-box approach to solving NP-complete problems in square-root as much time as is required classically.
“That this was a real possibility is clear from Grover's [13] result, which gives a black-box approach to solving NP -complete problems in square-root as much time as is required classically.”
From Strengths and Weaknesses of Quantum Computing (1997) · cites this paper as [13]
Inversion about the average changes the phase difference into an amplitude difference, leaving the y term with the same sign as all the other terms but a magnitude approximately threefold larger.
“Various strategies can be imagined, but a good one (called 'inversion about the average' by Grover [13]) is to perform an oracle-independent unitary transformation so as to change the phase difference into an amplitude difference, leaving the y term with the same sign as all the other terms but a magnitude approximately threefold larger.”
From Strengths and Weaknesses of Quantum Computing (1997) · cites this paper as [13]
The HNDL adversary departs from conventional cryptanalysis in its temporal asymmetry: instead of attempting immediate decryption, the attacker passively collects encrypted traffic or stored archives and defers decryption until sufficient computational resources become available.
“The HNDL adversary departs from conventional cryptanalysis in its temporal asymmetry. Instead of attempting immediate decryption, the attacker passively collects encrypted traffic or stored archives and defers decryption until sufficient computational resources become available.”
From Harvest-Now, Decrypt-Later: A Temporal Cybersecurity Risk in the Quantum Transition (2025) · cites this paper as [13]
Split into 2 atoms — 0 confirmed, 0 partially supported, 0 disputed, 0 misattributed, 2 unverifiable. Expand the claim to see per-atom verdicts.
Experimental — accuracy not yet measuredThe algorithm uses a single function evaluation to label the single state which satisfies the function, followed by a series of gates which drive the system into this particular state.
“This algorithm uses a single function evaluation to label the single state which satisfies the function, followed by a series of gates which drive the system into this particular state.”
From Implementation of a quantum search algorithm on a quantum computer (1998) · cites this paper as [9]
The authors implemented a quantum search algorithm (Grover's) on a two-qubit NMR quantum computer.
“Here we show how such a computer can be used to implement a fast quantum search algorithm initially developed by Grover. 9, 10”
From Implementation of a quantum search algorithm on a quantum computer (1998) · cites this paper as [9]
Grover's algorithms enable an extremely rapid search over the domain of a binary function to find elements for which the function is satisfied.
“Among other applications Grover's algorithms enable an extremely rapid search over the domain of a binary function to find elements for which this function is satisfied (that is, the function has the value 1).”
From Implementation of a quantum search algorithm on a quantum computer (1998) · cites this paper as [9]
Hamiltonian simulation can be used with the quantum phase estimation algorithm to efficiently obtain the eigen-energies and eigenstates of a quantum system.
“the ability to efficiently perform Hamiltonian simulation is used in conjunction with another technique known as the quantum phase estimation algorithm (QPEA) 42 for efficiently obtaining the eigen-energies and eigenstates of a quantum system 38 .”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [38]
The quantum phase estimation algorithm is the natural translation of the FCI procedure to quantum computers.
“The Quantum Phase Estimation (QPE) algorithm 38,99 is the natural translation of the FCI procedure to quantum computers 45 .”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [38]
Abrams and Lloyd described concrete initialization procedures for state preparation.
“Abrams and Lloyd 38 focused on state preparation in more detail and described concrete initialization procedures.”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [38]
State preparation is conceptually easier in second quantization, where a Fock state is represented by a simple product state of qubits in {|0>, |1>} states.
“They pointed out that state preparation is conceptually easier in second quantization, where a Fock state is represented by a simple product state of qubits in {| 0 〉 , | 1 〉} states.”
From Quantum Chemistry in the Age of Quantum Computing (2019) · cites this paper as [38]
Cites
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713 · see citing works
Quantum theory, the Church–Turing principle and the universal quantum computer
Deutsch, D. (1985) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1985.0070 · Cited by 4,597 · see citing works
Scheme for reducing decoherence in quantum computer memory
Shor, P. W. (1995) · Physical Review A · doi:10.1103/physreva.52.r2493 · Cited by 4,479 · see citing works
Rapid solution of problems by quantum computation
Deutsch, D., & Jozsa, R. (1992) · Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences · doi:10.1098/rspa.1992.0167 · Cited by 2,700 · see citing works
The Emperor's New Mind: Concerning Computers, Minds, and The Laws of Physics
Penrose, R., & Gardner, M. (1989) · doi:10.1093/oso/9780198519737.001.0001 · Cited by 2,007 · see citing works
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470 · see citing works
On the Power of Quantum Computation
Simon, D. R. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796298637 · Cited by 1,295 · see citing works
Bernstein, E., & Vazirani, U. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167097 · Cited by 1,284 · see citing works
Benioff, P. (1980) · Journal of Statistical Physics · doi:10.1007/bf01011339 · Cited by 1,244 · see citing works
<i>The Emperor's New Mind: Concerning Computers, Minds, and the Laws of Physics</i>
Penrose, R., & Landauer, R. (1990) · Physics Today · doi:10.1063/1.2810599 · Cited by 1,110 · see citing works
(1996) · Cited by 824 · see citing works
NP is as easy as detecting unique solutions
Valiant, L. G., & Vazirani, V. V. (1986) · Theoretical Computer Science · doi:10.1016/0304-3975(86)90135-0 · Cited by 645 · see citing works
Yao, A. C.-C. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1993.366852 · Cited by 639 · see citing works
Matching is as easy as matrix inversion
Mulmuley, K., Vazirani, U. V., & Vazirani, V. V. (1987) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/28395.383347 · Cited by 611 · see citing works
On the power of quantum computation
Simon, D. R. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365701 · Cited by 491 · see citing works
QUANTUM MECHANICAL INTERACTION-FREE MEASUREMENTSPreprint
Elitzur, A. C., & Lev Vaidman, A. (1993) · Cited by 463 · see citing works
The emperor's new mind concerning computers, minds, and the laws of physics
(1990) · Choice Reviews Online · doi:10.5860/choice.27-4496 · Cited by 440 · see citing works
Matching is as easy as matrix inversion
Mulmuley, K., Vazirani, U. V., & Vazirani, V. V. (1987) · COMBINATORICA · doi:10.1007/bf02579206 · Cited by 388 · see citing works
A Quantum Algorithm for Finding the Minimum
Durr, C., & Hoyer, P. (1996) · arXiv · doi:10.48550/arxiv.quant-ph/9607014 · Cited by 359 · see citing works
Efficient networks for quantum factoring
Beckman, D., Chari, A. N., Devabhaktuni, S., & Preskill, J. (1996) · Physical Review A · doi:10.1103/physreva.54.1034 · Cited by 268 · see citing works
Berthiaume, A., & Brassard, G. (1994) · Journal of Modern Optics · doi:10.1080/09500349414552351 · Cited by 99 · see citing works
The quantum challenge to structural complexity theory
Berthiaume, A., & Brassard, G. (2003) · Structure in Complexity Theory Annual Conference · doi:10.1109/sct.1992.215388 · Cited by 73 · see citing works
Kwiat, P. G., Weinfurter, H., & Zeilinger, A. (1996) · Scientific American · doi:10.1038/scientificamerican1196-72 · Cited by 57 · see citing works
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., et al. (1997) · doi:10.48550/arxiv.quant-ph/9701001 · Cited by 23 · see citing works
Flagged first, then by citations
Research works printed but not linked: 2
- [9]9. R. Penrose, Shadows of the mind,. Oxford University Press, 1994, pp. 348- 388.
- [14]14. Yao93J A. Yao, Quantum circuit complexip, Proceedings 34th Annual Symposium on Foundations of Computer Science (FOCS), 1993, pp. 352-361.
Cited by
Sorted by citations
A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
Farhi, E., Goldstone, J., Gutmann, S., Lapan, J., Lundgren, A., & Preda, D. (2001) · Science · doi:10.1126/science.1057726 · Cited by 2,056 · see citing works
Measurement-based quantum computation on cluster states
Raussendorf, R., Browne, D. E., & Briegel, H. J. (2003) · Physical Review A · doi:10.1103/physreva.68.022312 · Cited by 1,655 · see citing works
Quantum-inspired evolutionary algorithm for a class of combinatorial optimization
Han, K.-H., & Kim, J.-H. (2002) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2002.804320 · Cited by 1,601 · see citing works
Quantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J. P., Degroote, M., Johnson, P. D., Kieferová, M., Kivlichan, I. D., Menke, T., Peropadre, B., Sawaya, N. P. D., et al. (2019) · Chemical Reviews · doi:10.1021/acs.chemrev.8b00803 · Cited by 1,560 · see citing works
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470 · see citing works
Quantum amplitude amplification and estimation
Brassard, G., Høyer, P., Mosca, M., & Tapp, A. (2002) · Contemporary Mathematics · doi:10.1090/conm/305/05215 · Cited by 1,680 · see citing works
Quantum random walks: An introductory overview
Kempe, J. (2003) · Contemporary Physics · doi:10.1080/00107151031000110776 · Cited by 1,413 · see citing works
6G and Beyond: The Future of Wireless Communications Systems
Akyildiz, I. F., Kak, A., & Nie, S. (2020) · IEEE Access · doi:10.1109/access.2020.3010896 · Cited by 1,419 · see citing works
Cleve, R., EKERT, A. K., Macchiavello, C., & Mosca, M. (1998) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.1998.0164 · Cited by 1,279 · see citing works
Bernstein, E., & Vazirani, U. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167097 · Cited by 1,284 · see citing works
Stabilizer Codes and Quantum Error Correction
Gottesman, D. (1997) · arXiv · doi:10.48550/arxiv.quant-ph/9705052 · Cited by 753 · see citing works
Bernstein, D. J., & Lange, T. (2017) · Nature · doi:10.1038/nature23461 · Cited by 1,242 · see citing works
Quantum Chemistry in the Age of Quantum Computing
Cao, Y., Romero, J., Olson, J., Degroote, M., Johnson, P., Kieferová, M., Kivlichan, I., Menke, T., Peropadre, B., Sawaya, N., et al. (n.d.) · OPUS - Open Publications of UTS Scholars (University of Technology Sydney) · Cited by 1,265 · see citing works
The role of relative entropy in quantum information theory
Vedral, V. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.197 · Cited by 1,140 · see citing works
CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM
Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., & Stehle, D. (2018) · 2018 IEEE European Symposium on Security and Privacy (EuroS&P) · doi:10.1109/eurosp.2018.00032 · Cited by 1,192 · see citing works
Machine learning & artificial intelligence in the quantum domain: a review of recent progress
Dunjko, V., & Briegel, H. J. (2018) · Reports on Progress in Physics · doi:10.1088/1361-6633/aab406 · Cited by 1,132 · see citing works
The Variational Quantum Eigensolver: A review of methods and best practices
Tilly, J., Chen, H., Cao, S., Picozzi, D., Setia, K., Li, Y., Grant, E., Wossnig, L., Rungger, I., Booth, G. H., et al. (2022) · Physics Reports · doi:10.1016/j.physrep.2022.08.003 · Cited by 1,031 · see citing works
Quantum walks: a comprehensive review
Venegas-Andraca, S. E. (2012) · Quantum Information Processing · doi:10.1007/s11128-012-0432-5 · Cited by 925 · see citing works
Quantum random walks - an introductory overview
Kempe, J., & Einstein, A. (2003) · Cited by 1,035 · see citing works
Hamiltonian Simulation by Qubitization
Low, G. H., & Chuang, I. L. (2019) · Quantum · doi:10.22331/q-2019-07-12-163 · Cited by 854 · see citing works
On the role of entanglement in quantum-computational speed-up
Jozsa, R., & Linden, N. (2003) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2002.1097 · Cited by 839 · see citing works
Le, P. Q., Dong, F., & Hirota, K. (2010) · Quantum Information Processing · doi:10.1007/s11128-010-0177-y · Cited by 797 · see citing works
Power of data in quantum machine learning
Huang, H.-Y., Broughton, M., Mohseni, M., Babbush, R., Boixo, S., Neven, H., & McClean, J. R. (2021) · Nature Communications · doi:10.1038/s41467-021-22539-9 · Cited by 896 · see citing works
NEQR: a novel enhanced quantum representation of digital images
Zhang, Y., Lü, K., Gao, Y., & Wang, M. (2013) · Quantum Information Processing · doi:10.1007/s11128-013-0567-z · Cited by 731 · see citing works
Quantum Walk Algorithm for Element Distinctness
Ambainis, A. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447311 · Cited by 727 · see citing works
Challenges and opportunities in quantum machine learning
Cerezo, M., Verdon, G., Huang, H.-Y., Cincio, Ł., & Coles, P. J. (2022) · Nature Computational Science · doi:10.1038/s43588-022-00311-3 · Cited by 735 · see citing works
Quantum computing for finance: Overview and prospects
Orús, R., Mugel, S., & Lizaso, E. (2019) · Reviews in Physics · doi:10.1016/j.revip.2019.100028 · Cited by 714 · see citing works
Genetic quantum algorithm and its application to combinatorial optimization problem
Han, K.-H., & Kim, J.-H. (2002) · IEEE Congress on Evolutionary Computation (CEC) · doi:10.1109/cec.2000.870809 · Cited by 675 · see citing works
Complexity measures and decision tree complexity: a survey
Buhrman, H., & de Wolf, R. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(01)00144-x · Cited by 668 · see citing works
Hamiltonian Simulation by Qubitization
Low, G. H., & Chuang, I. L. (2019) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 714 · see citing works
QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS
AMBAINIS, A. (2003) · International Journal of Quantum Information · doi:10.1142/s0219749903000383 · Cited by 632 · see citing works
Childs, A. M., Kothari, R., & Somma, R. D. (2017) · SIAM Journal on Computing · doi:10.1137/16m1087072 · Cited by 646 · see citing works
Gilyén, A., Su, Y., Low, G. H., & Wiebe, N. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316366 · Cited by 685 · see citing works
Quantum lower bounds by polynomials
Beals, R., Buhrman, H., Cleve, R., Mosca, M., & de Wolf, R. (2001) · Journal of the ACM · doi:10.1145/502090.502097 · Cited by 639 · see citing works
Grover’s quantum searching algorithm is optimal
Zalka, C. (1999) · Physical Review A · doi:10.1103/physreva.60.2746 · Cited by 635 · see citing works
Aharonov, D., Ambainis, A., Kempe, J., & Vazirani, U. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380758 · Cited by 654 · see citing works
Nonlocality and communication complexity
Buhrman, H., Cleve, R., Massar, S., & de Wolf, R. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.665 · Cited by 612 · see citing works
Fernandez-Carames, T. M., & Fraga-Lamas, P. (2020) · IEEE Access · doi:10.1109/access.2020.2968985 · Cited by 607 · see citing works
6G Wireless Communications Networks: A Comprehensive Survey
Alsabah, M. Q., Naser, M. A., Mahmmod, B. M., Abdulhussain, S. H., Eissa, M. R., Al-Baidhani, A., Noordin, N. K., Sait, S. M., Al-Utaibi, K. A., & Hashim, F. (2021) · IEEE Access · doi:10.1109/access.2021.3124812 · Cited by 593 · see citing works
Tackling the Qubit Mapping Problem for NISQ-Era Quantum Devices
Li, G., Ding, Y., & Xie, Y. (2019) · Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/3297858.3304023 · Cited by 594 · see citing works
Cybersecurity in an Era with Quantum Computers: Will We Be Ready?
Mosca, M. (2018) · IEEE Security & Privacy · doi:10.1109/msp.2018.3761723 · Cited by 581 · see citing works
Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., & Watrous, J. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380757 · Cited by 562 · see citing works
Implementation of a quantum search algorithm on a quantum computer
Jones, J. A., Mosca, M., & Hansen, R. H. (1998) · Nature · doi:10.1038/30687 · Cited by 558 · see citing works
Information and computation: Classical and quantum aspects
Galindo, A., & Martin-Delgado, M. A. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.347 · Cited by 545 · see citing works
Coelho, L. D. S. (2009) · Expert Systems with Applications · doi:10.1016/j.eswa.2009.06.044 · Cited by 547 · see citing works
Quantum Computation by Adiabatic Evolution
Farhi, E., Goldstone, J., Gutmann, S., & Sipser, M. (2000) · arXiv · doi:10.48550/arxiv.quant-ph/0001106 · Cited by 536 · see citing works
Universal quantum computation using the discrete-time quantum walk
Lovett, N. B., Cooper, S., Everitt, M., Trevers, M., & Kendon, V. (2010) · Physical Review A · doi:10.1103/physreva.81.042330 · Cited by 510 · see citing works
Quantum entanglement of the spin and orbital angular momentum of photons using metamaterials
Stav, T., Faerman, A., Maguid, E., Oren, D., Kleiner, V., Hasman, E., & Segev, M. (2018) · Science · doi:10.1126/science.aat9042 · Cited by 502 · see citing works
CSIDH: An Efficient Post-Quantum Commutative Group Action
Castryck, W., Lange, T., Martindale, C., Panny, L., & Renes, J. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-03332-3_15 · Cited by 497 · see citing works
Schlosshauer, M. (2019) · Physics Reports · doi:10.1016/j.physrep.2019.10.001 · Cited by 521 · see citing works
Quantum computing: A taxonomy, systematic review and future directions
Gill, S. S., Kumar, A., Singh, H., Singh, M., Kaur, K., Usman, M., & Buyya, R. (2021) · Software Practice and Experience · doi:10.1002/spe.3039 · Cited by 531 · see citing works
Han, K.-H., & Kim, J.-H. (2004) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2004.823467 · Cited by 485 · see citing works
Towards a quantum programming language
Selinger, P. (2004) · Mathematical Structures in Computer Science · doi:10.1017/s0960129504004256 · Cited by 459 · see citing works
Demonstration of Blind Quantum Computing
Barz, S., Kashefi, E., Broadbent, A., Fitzsimons, J. F., Zeilinger, A., & Walther, P. (2012) · Science · doi:10.1126/science.1214707 · Cited by 475 · see citing works
Variational Quantum Computation of Excited States
Higgott, O., Wang, D., & Brierley, S. (2019) · Quantum · doi:10.22331/q-2019-07-01-156 · Cited by 463 · see citing works
Random Oracles in a Quantum World
Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., & Zhandry, M. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-25385-0_3 · Cited by 467 · see citing works
Ascon v1.2: Lightweight Authenticated Encryption and Hashing
Dobraunig, C., Eichlseder, M., Mendel, F., & Schläffer, M. (2021) · Journal of Cryptology · doi:10.1007/s00145-021-09398-9 · Cited by 478 · see citing works
Quantum walks: a comprehensive reviewPreprint
Venegas-Andraca, S. E. (2012) · Cited by 533 · see citing works
Quantum optimization of maximum independent set using Rydberg atom arrays
Ebadi, S., Keesling, A., Cain, M., Wang, T. T., Levine, H., Bluvstein, D., Semeghini, G., Omran, A., Liu, J.-G., Samajdar, R., et al. (2022) · Science · doi:10.1126/science.abo6587 · Cited by 430 · see citing works
ProjectQ: An open source software framework for quantum computing
Steiger, D. S., Häner, T., & Troyer, M. (2018) · Quantum · doi:10.22331/q-2018-01-31-49 · Cited by 428 · see citing works
Deterministic generation of a cluster state of entangled photons
Schwartz, I., Cogan, D., Schmidgall, E. R., Don, Y., Gantz, L., Kenneth, O., Lindner, N. H., & Gershoni, D. (2016) · Science · doi:10.1126/science.aah4758 · Cited by 410 · see citing works
A review on Quantum Approximate Optimization Algorithm and its variants
Blekos, K., Brand, D., Ceschini, A., Chou, C.-H., Li, R.-H., Pandya, K., & Summer, A. (2024) · Physics Reports · doi:10.1016/j.physrep.2024.03.002 · Cited by 444 · see citing works
Status report on the third round of the NIST Post-Quantum Cryptography Standardization process
Alagic, G., Apon, D., Cooper, D. A., Dang, Q. H., Dang, T., Kelsey, J. M., Lichtinger, J., Liu, Y.-K., Miller, C. A., Moody, D., et al. (2022) · doi:10.6028/nist.ir.8413 · Cited by 414 · see citing works
An introduction to quantum computing for non-physicists
Rieffel, E. G., & Polak, W. (2000) · ACM Computing Surveys · doi:10.1145/367701.367709 · Cited by 436 · see citing works
Quantum machine learning: a classical perspective
Ciliberto, C., Herbster, M., Ialongo, A. D., Pontil, M., Rocchetto, A., Severini, S., & Wossnig, L. (2018) · Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.2017.0551 · Cited by 518 · see citing works
Quantum vs. classical communication and computation
Buhrman, H., Cleve, R., & Wigderson, A. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276713 · Cited by 394 · see citing works
Simulating quantum systems on a quantum computer
Zalka, C. (1998) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.1998.0162 · Cited by 387 · see citing works
Wireless Myths, Realities, and Futures: From 3G/4G to Optical and Quantum Wireless
Hanzo, L., Haas, H., Imre, S., O'Brien, D. C., Rupp, M., & Gyöngyösi, L. (2012) · Proceedings of the IEEE · doi:10.1109/jproc.2012.2189788 · Cited by 384 · see citing works
Analog analogue of a digital quantum computation
Farhi, E., & Gutmann, S. (1998) · Physical Review A · doi:10.1103/physreva.57.2403 · Cited by 389 · see citing works
Zero Trust Architecture (ZTA): A Comprehensive Survey
Syed, N. F., Shah, S. W., Shaghaghi, A., Anwar, A., Baig, Z., & Doss, R. (2022) · IEEE Access · doi:10.1109/access.2022.3174679 · Cited by 406 · see citing works
“Similarly, for hash functions, Grover’s algorithm [185] can facilitate quantum birthday attack to find collision, thereby necessitating an output of larger size.”
BackgroundAn Efficient Methodology for Mapping Quantum Circuits to the IBM QX Architectures
Zulehner, A., Paler, A., & Wille, R. (2018) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2018.2846658 · Cited by 382 · see citing works
Quantum Reinforcement Learning
Dong, D., Chen, C., Li, H., & Tarn, T.-J. (2008) · IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) · doi:10.1109/tsmcb.2008.925743 · Cited by 410 · see citing works
Verified quantum information scrambling
Landsman, K. A., Figgatt, C., Schuster, T., Linke, N. M., Yoshida, B., Yao, N. Y., & Monroe, C. (2019) · Nature · doi:10.1038/s41586-019-0952-6 · Cited by 368 · see citing works
A Quantum Algorithm for Finding the Minimum
Durr, C., & Hoyer, P. (1996) · arXiv · doi:10.48550/arxiv.quant-ph/9607014 · Cited by 359 · see citing works
Operating Quantum States in Single Magnetic Molecules: Implementation of Grover’s Quantum Algorithm
Godfrin, C., Ferhat, A., Ballou, R., Klyatskaya, S. V., Ruben, M., Wernsdorfer, W., & Balestro, F. (2017) · Physical Review Letters · doi:10.1103/physrevlett.119.187702 · Cited by 354 · see citing works
Quantum information processing and communication
Zoller, P., Beth, T., Binosi, D., Blatt, R., Briegel, H. J., Bruss, D., Calarco, T., Cirac, J. I., Deutsch, D., Eisert, J., et al. (2005) · The European Physical Journal D · doi:10.1140/epjd/e2005-00251-1 · Cited by 350 · see citing works
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 342 · see citing works
On the power of quantum finite state automata
Kondacs, A., & Watrous, J. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646094 · Cited by 356 · see citing works
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344 · see citing works
Breaking Symmetric Cryptosystems Using Quantum Period Finding
Kaplan, M. A., Leurent, G., Leverrier, A., & Naya‐Plasencia, M. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53008-5_8 · Cited by 347 · see citing works
Quantum Lower Bounds by Quantum Arguments
Ambainis, A. (2002) · Journal of Computer and System Sciences · doi:10.1006/jcss.2002.1826 · Cited by 345 · see citing works
Quantum annealing for industry applications: introduction and review
Yarkoni, S., Raponi, E., Bäck, T., & Schmitt, S. (2022) · Reports on Progress in Physics · doi:10.1088/1361-6633/ac8c54 · Cited by 341 · see citing works
Strawberry Fields: A Software Platform for Photonic Quantum Computing
Killoran, N., Izaac, J., Quesada, N., Bergholm, V., Amy, M., & Weedbrook, C. (2019) · Quantum · doi:10.22331/q-2019-03-11-129 · Cited by 327 · see citing works
Quantum lower bounds for the collision and the element distinctness problems
Aaronson, S., & Shi, Y. (2004) · Journal of the ACM · doi:10.1145/1008731.1008735 · Cited by 323 · see citing works
Kavokin, A. V., Baumberg, J. J., Malpuech, G., & Laussy, F. P. (2017) · doi:10.1093/oso/9780198782995.001.0001 · Cited by 326 · see citing works
The status of the P versus NP problem
Fortnow, L. (2009) · Communications of the ACM · doi:10.1145/1562164.1562186 · Cited by 330 · see citing works
Bos, J. W., Costello, C., Ducas, L., Mironov, I., Naehrig, M., Nikolaenko, V., Raghunathan, A., & Stebila, D. (2016) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2976749.2978425 · Cited by 324 · see citing works
Fernández‐Caramés, T. M. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2958788 · Cited by 340 · see citing works
A survey of quantum image representations
Yan, F., Iliyasu, A. M., & Venegas-Andraca, S. E. (2015) · Quantum Information Processing · doi:10.1007/s11128-015-1195-6 · Cited by 308 · see citing works
Magnetic qubits as hardware for quantum computers
Tejada, J., Chudnovsky, E. M., del Barco, E., Hernández, J. M., & Spiller, T. P. (2001) · Nanotechnology · doi:10.1088/0957-4484/12/2/323 · Cited by 306 · see citing works
Quantum Machine Learning: What Quantum Computing Means to Data Mining
Wittek, P. (2014) · Cited by 319 · see citing works
Applying Grover’s Algorithm to AES: Quantum Resource Estimates
Grassl, M., Langenberg, B., Roetteler, M., & Steinwandt, R. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-29360-8_3 · Cited by 299 · see citing works
Random Walks: A Review of Algorithms and Applications
Xia, F., Liu, J., Nie, H., Fu, Y., Wan, L., & Kong, X. (2020) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2019.2952908 · Cited by 295 · see citing works
Magniez, F., Nayak, A., Roland, J., & Santha, M. (2011) · SIAM Journal on Computing · doi:10.1137/090745854 · Cited by 294 · see citing works
Herman, D., Googin, C., Liu, X., Sun, Y., Galda, A., Safro, I., Pistoia, M., & Alexeev, Y. (2023) · Nature Reviews Physics · doi:10.1038/s42254-023-00603-1 · Cited by 310 · see citing works
Processing images in entangled quantum systems
Venegas-Andraca, S. E., & Ball, J. L. (2009) · Quantum Information Processing · doi:10.1007/s11128-009-0123-z · Cited by 290 · see citing works
Global Entanglement in Multiparticle SystemsPreprint
MEYER, D. A., Wallach, N. R., & Wallach, M. (2001) · Cited by 319 · see citing works
Status report on the third round of the NIST Post-Quantum Cryptography Standardization process
Alagic, G., Apon, D., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y.-K., Miller, C., Moody, D., et al. (2022) · doi:10.6028/nist.ir.8413-upd1 · Cited by 301 · see citing works
Ventura, D. A. (2000) · Information Sciences · doi:10.1016/s0020-0255(99)00101-2 · Cited by 284 · see citing works
Quantum computation and quantum information
Nagy, M., & Akl, S. G. (2005) · International Journal of Parallel Emergent and Distributed Systems · doi:10.1080/17445760500355678 · Cited by 320 · see citing works
- Authors
- Grover, L. K.
- Affiliations
- AT&T (United States) (US)
- Corresponding author
- Grover, Lov K.
- Venue
- Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96
- Publisher
- ACM Press
- Published
- 1996
- Pages
- 212-219
- OpenAlex
- W2084652510
- Semantic Scholar
- 298d799da82395a64a3bda38ef9d2a4646828ccb
- Cited by
- 8,830
- References
- 24
- Citations by year
- 2026: 664 · 2025: 1066 · 2024: 896 · 2023: 841 · 2022: 674 · 2021: 655 · 2020: 529 · 2019: 423 · 2018: 288 · 2017: 283 · 2016: 219 · 2015: 221 · 2014: 184 · 2013: 161 · 2012: 158
- FWCI
- 36.24
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- ACM Symposium on Theory of Computing (STOC) (publishedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
- Keywords
- quantum search, unsorted database search, Grover's algorithm, quantum algorithms, time complexity, quantum parallelism, lower bounds
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-21.
Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-21.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
