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

Quantum Reports

Entanglement in Quantum Search Database: Periodicity Variations and Counting

Demosthenes Ellinas, Christos Konstandakis

Published Jul 22, 2022• 0 citations
Publisher

Abstract

Employing the single item search algorithm of N dimensional database it is shown that: First, the entanglement developed between two any-size parts of database space varies periodically during the course of searching. The periodic entanglement of the associated reduced density matrix quantified by several entanglement measures (linear entropy, von Neumann, Renyi), is found to vanish with period O(sqrt(N)). Second, functions of equal entanglement are shown to vary also with equal period. Both those phenomena, based on size-independent database bi-partition, manifest a general scale invariant property of entanglement in quantum search. Third, measuring the entanglement periodicity via the number of searching steps between successive canceling out, determines N, the database set cardinality, quadratically faster than ordinary counting. An operational setting that includes an Entropy observable and its quantum circuits realization is also provided for implementing fast counting. Rigging the marked item initial probability, either by initial advice or by guessing, improves hyper-quadratically the performance of those phenomena.

DOI
10.3390/quantum4030015

Related papers

Entanglement in the Grover's Search Algorithm

Shantanav Chakraborty, Subhashish Banerjee, Satyabrata Adhikari +1 more

Quantum Algorithms have long captured the imagination of computer scientists and physicists primarily because of the speed up achieved by them over their classical counterparts using principles of quantum mechanics. Entanglement is believed to be the primary phenomena behind this speed up. However their precise role in quantum algorithms is yet unclear. In this article, we explore the nature of entanglement in the Grover's search algorithm. This algorithm enables searching of elements from an unstructured database quadratically faster than the best known classical algorithm. Geometric measure of entanglement has been used to quantify and analyse entanglement across iterations of the algorithm. We reveal how the entanglement varies with increase in the number of qubits and also with the number of marked or solution states. Numerically, it is seen that the behaviour of the maximum value of entanglement is monotonous with the number of qubits. Also, for a given value of the number of qubits, a change in the marked states alters the amount of entanglement. The amount of entanglement in the final state of the algorithm has been shown to depend solely on the nature of the marked states. Explicit analytical expressions are given showing the variation of entanglement with the number of iterations and the global maximum value of entanglement attained across all iterations of the algorithm.

arXiv:1305.4454•May 20, 2013•9 citations

Coherence and Entanglement Monogamy in the Discrete Analogue of Analog Grover Search

Namit Anand, Arun Kumar Pati

Grover's search algorithm is the optimal quantum algorithm that can search an unstructured database quadratically faster than any known classical algorithm. The role of entanglement and correlations in the search algorithm have been studied in great detail and it is known that entanglement between the qubits is necessary to gain a quadratic speedup, for pure state implementation of the Grover search algorithm. Here, we systematically investigate the behavior of quantum coherence and monogamy of entanglement in the discrete analogue of the $\textit{analog analogue of Grover search algorithm}$. The analog analogue of Grover search is a continuous time quantum algorithm based on the adiabatic Hamiltonian evolution that gives a quadratic speedup, similar to the original Grover search algorithm. We show that the decrease of quantum coherence, quantified using various coherence monotones, is a clear signature of attaining the maximum success probability in the analog Grover search. We also show that for any two qubit reduced density matrix of the system, the concurrence evolves in close vicinity to the increasing rate of success probability. Furthermore, we show that the system satisfies a $n$-party monogamy inequality for arbitrary times, hence bounding the amount of $n$-qubit entanglement during the quantum search.

arXiv:1611.04542•Nov 14, 2016•24 citations

Entanglement, and Unsorted Database Search in Noise-Based Logic

László B. Kish, Walter C. Daugherity

We explore the collapse of “wavefunction” and the measurement of entanglement in the superpositions of hyperspace vectors in classical physical instantaneous-noise-based logic (INBL). We find both similarities with and major differences from the related properties of quantum systems. Two search algorithms utilizing the observed features are introduced. For the first one we assume an unsorted names database set up by Alice that is a superposition (unknown by Bob) of up to n = 2N strings; those we call names. Bob has access to the superposition wave and to the 2N reference noises of the INBL system of N noise bits. For Bob, to decide if a given name x is included in the superposition, once the search has begun, it takes N switching operations followed by a single measurement of the superposition wave. Thus, the time and hardware complexity of the search algorithm is O[log(n)], which indicates an exponential speedup compared to Grover’s quantum algorithm in a corresponding setting. An extra advantage is that the error probability of the search is zero. Moreover, the scheme can also check the existence of a fraction of a string, or several separate string fractions embedded in an arbitrarily long, arbitrary string. In the second algorithm, we expand the above scheme to a phonebook with n names and s phone numbers. When the names and numbers have the same bit resolution, once the search has begun, the time and hardware complexity of this search algorithm is O[log(n)]. In the case of one-to-one correspondence between names and phone numbers (n = s), the algorithm offers inverse phonebook search too. The error probability of this search algorithm is also zero.

arXiv:1905.03162•Applied Sciences•Jul 27, 2019•10 citations

Quantum Search in Hilbert Space

Michail A. Zak

A proposed quantum-computing algorithm would perform a search for an item of information in a database stored in a Hilbert-space memory structure. The algorithm is intended to make it possible to search relatively quickly through a large database under conditions in which available computing resources would otherwise be considered inadequate to perform such a task. The algorithm would apply, more specifically, to a relational database in which information would be stored in a set of N complex orthonormal vectors, each of N dimensions (where N can be exponentially large). Each vector would constitute one row of a unitary matrix, from which one would derive the Hamiltonian operator (and hence the evolutionary operator) of a quantum system. In other words, all the stored information would be mapped onto a unitary operator acting on a quantum state that would represent the item of information to be retrieved. Then one could exploit quantum parallelism: one could pose all search queries simultaneously by performing a quantum measurement on the system. In so doing, one would effectively solve the search problem in one computational step. One could exploit the direct- and inner-product decomposability of the unitary matrix to make the dimensionality of the memory space exponentially large by use of only linear resources. However, inasmuch as the necessary preprocessing (the mapping of the stored information into a Hilbert space) could be exponentially expensive, the proposed algorithm would likely be most beneficial in applications in which the resources available for preprocessing were much greater than those available for searching.

•Jan 1, 2003•0 citations

Analysis of Grover’s quantum search algorithm as a dynamical system

Ofer Biham, Daniel Shapira, Yishai Shimoni

Grover's quantum search algorithm is analyzed for the case in which the initial state is an arbitrary pure quantum state $|\ensuremath{\varphi}〉$ of n qubits. It is shown that the optimal time to perform the measurement is independent of $|\ensuremath{\varphi}〉,$ namely, it is identical to the optimal time in the original algorithm in which $|\ensuremath{\varphi}〉=|0〉,$ with the same number of marked states, r. The probability of success ${P}_{\mathrm{s}}$ is obtained in terms of the amplitudes of the state $|\ensuremath{\varphi}〉$ and is shown to be independent of r. A class of states, which includes fixed points and cycles of the Grover iteration operator, is identified. The relevance of these results in the context of using the success probability as an entanglement measure is discussed. In particular, the Groverian entanglement measure, previously limited to a single marked state, is generalized to the case of several marked states.

arXiv:quant-ph/0307141•Physical Review A•Aug 29, 2003•15 citations

Quantum Multi-object Search Algorithm with the Availability of Partial Information

Goong Chen, Zijian Diao

Abstract Consider the unstructured search of an unknown number I of items in a large unsorted database of size N. The multi-object quantum search algorithm consists of two parts. The first part of the algorithm is to generalize Grover's single-object search algorithm to the multi-object case, and the second part is to solve a counting problem to determine l. In this paper we study the multi-object quantum search algorithm (in continuous time), but in a more structured way by taking into account the availability of partial information. The modeling of available partial information is done simply by the combination of several pre­scribed, possibly overlapping, information sets with varying weights to signify the reliability of each set. The associated statistics is estimated and the algorithm efficiency and complexity are analyzed. Our analysis shows that the search described here may not be more efficient than the unstructured (generalized) multi-object Grover search if there is "misplaced confidence". However, if the information sets have a "basic confidence" property in the sense that each information set contains at least one search item, then a quadratic speedup holds on a much smaller data space, which further expedites the quantum search for the first item.

arXiv:quant-ph/0011019•Zeitschrift für Naturforschung A•Dec 1, 2001•0 citations
Employing the single item search algorithm of N dimensional database it is shown that: First, the entanglement developed between two any-size parts of database space varies periodically during the course of searching. The periodic entanglement of the associated reduced density matrix quantified by several entanglement measures (linear entropy, von Neumann, Renyi), is found to vanish with period O(sqrt(N)). Second, functions of equal entanglement are shown to vary also with equal period. Both those phenomena, based on size-independent database bi-partition, manifest a general scale invariant property of entanglement in quantum search. Third, measuring the entanglement periodicity via the number of searching steps between successive canceling out, determines N, the database set cardinality, quadratically faster than ordinary counting. An operational setting that includes an Entropy observable and its quantum circuits realization is also provided for implementing fast counting. Rigging the marked item initial probability, either by initial advice or by guessing, improves hyper-quadratically the performance of those phenomena.
Quantum Algorithms have long captured the imagination of computer scientists and physicists primarily because of the speed up achieved by them over their classical counterparts using principles of quantum mechanics. Entanglement is believed to be the primary phenomena behind this speed up. However their precise role in quantum algorithms is yet unclear. In this article, we explore the nature of entanglement in the Grover's search algorithm. This algorithm enables searching of elements from an unstructured database quadratically faster than the best known classical algorithm. Geometric measure of entanglement has been used to quantify and analyse entanglement across iterations of the algorithm. We reveal how the entanglement varies with increase in the number of qubits and also with the number of marked or solution states. Numerically, it is seen that the behaviour of the maximum value of entanglement is monotonous with the number of qubits. Also, for a given value of the number of qubits, a change in the marked states alters the amount of entanglement. The amount of entanglement in the final state of the algorithm has been shown to depend solely on the nature of the marked states. Explicit analytical expressions are given showing the variation of entanglement with the number of iterations and the global maximum value of entanglement attained across all iterations of the algorithm.
Grover's search algorithm is the optimal quantum algorithm that can search an unstructured database quadratically faster than any known classical algorithm. The role of entanglement and correlations in the search algorithm have been studied in great detail and it is known that entanglement between the qubits is necessary to gain a quadratic speedup, for pure state implementation of the Grover search algorithm. Here, we systematically investigate the behavior of quantum coherence and monogamy of entanglement in the discrete analogue of the analog analogue of Grover search algorithm\textit{analog analogue of Grover search algorithm}analog analogue of Grover search algorithm. The analog analogue of Grover search is a continuous time quantum algorithm based on the adiabatic Hamiltonian evolution that gives a quadratic speedup, similar to the original Grover search algorithm. We show that the decrease of quantum coherence, quantified using various coherence monotones, is a clear signature of attaining the maximum success probability in the analog Grover search. We also show that for any two qubit reduced density matrix of the system, the concurrence evolves in close vicinity to the increasing rate of success probability. Furthermore, we show that the system satisfies a nnn-party monogamy inequality for arbitrary times, hence bounding the amount of nnn-qubit entanglement during the quantum search.
We explore the collapse of “wavefunction” and the measurement of entanglement in the superpositions of hyperspace vectors in classical physical instantaneous-noise-based logic (INBL). We find both similarities with and major differences from the related properties of quantum systems. Two search algorithms utilizing the observed features are introduced. For the first one we assume an unsorted names database set up by Alice that is a superposition (unknown by Bob) of up to n = 2N strings; those we call names. Bob has access to the superposition wave and to the 2N reference noises of the INBL system of N noise bits. For Bob, to decide if a given name x is included in the superposition, once the search has begun, it takes N switching operations followed by a single measurement of the superposition wave. Thus, the time and hardware complexity of the search algorithm is O[log(n)], which indicates an exponential speedup compared to Grover’s quantum algorithm in a corresponding setting. An extra advantage is that the error probability of the search is zero. Moreover, the scheme can also check the existence of a fraction of a string, or several separate string fractions embedded in an arbitrarily long, arbitrary string. In the second algorithm, we expand the above scheme to a phonebook with n names and s phone numbers. When the names and numbers have the same bit resolution, once the search has begun, the time and hardware complexity of this search algorithm is O[log(n)]. In the case of one-to-one correspondence between names and phone numbers (n = s), the algorithm offers inverse phonebook search too. The error probability of this search algorithm is also zero.
A proposed quantum-computing algorithm would perform a search for an item of information in a database stored in a Hilbert-space memory structure. The algorithm is intended to make it possible to search relatively quickly through a large database under conditions in which available computing resources would otherwise be considered inadequate to perform such a task. The algorithm would apply, more specifically, to a relational database in which information would be stored in a set of N complex orthonormal vectors, each of N dimensions (where N can be exponentially large). Each vector would constitute one row of a unitary matrix, from which one would derive the Hamiltonian operator (and hence the evolutionary operator) of a quantum system. In other words, all the stored information would be mapped onto a unitary operator acting on a quantum state that would represent the item of information to be retrieved. Then one could exploit quantum parallelism: one could pose all search queries simultaneously by performing a quantum measurement on the system. In so doing, one would effectively solve the search problem in one computational step. One could exploit the direct- and inner-product decomposability of the unitary matrix to make the dimensionality of the memory space exponentially large by use of only linear resources. However, inasmuch as the necessary preprocessing (the mapping of the stored information into a Hilbert space) could be exponentially expensive, the proposed algorithm would likely be most beneficial in applications in which the resources available for preprocessing were much greater than those available for searching.
Grover's quantum search algorithm is analyzed for the case in which the initial state is an arbitrary pure quantum state $|\ensuremath{\varphi}〉$ of n qubits. It is shown that the optimal time to perform the measurement is independent of $|\ensuremath{\varphi}〉,$ namely, it is identical to the optimal time in the original algorithm in which $|\ensuremath{\varphi}〉=|0〉,$ with the same number of marked states, r. The probability of success Ps{P}_{\mathrm{s}}Ps​ is obtained in terms of the amplitudes of the state $|\ensuremath{\varphi}〉$ and is shown to be independent of r. A class of states, which includes fixed points and cycles of the Grover iteration operator, is identified. The relevance of these results in the context of using the success probability as an entanglement measure is discussed. In particular, the Groverian entanglement measure, previously limited to a single marked state, is generalized to the case of several marked states.
Abstract Consider the unstructured search of an unknown number I of items in a large unsorted database of size N. The multi-object quantum search algorithm consists of two parts. The first part of the algorithm is to generalize Grover's single-object search algorithm to the multi-object case, and the second part is to solve a counting problem to determine l. In this paper we study the multi-object quantum search algorithm (in continuous time), but in a more structured way by taking into account the availability of partial information. The modeling of available partial information is done simply by the combination of several pre­scribed, possibly overlapping, information sets with varying weights to signify the reliability of each set. The associated statistics is estimated and the algorithm efficiency and complexity are analyzed. Our analysis shows that the search described here may not be more efficient than the unstructured (generalized) multi-object Grover search if there is "misplaced confidence". However, if the information sets have a "basic confidence" property in the sense that each information set contains at least one search item, then a quadratic speedup holds on a much smaller data space, which further expedites the quantum search for the first item.