Some remarks on the Grover algorithm

We calculate the amount of entanglement of the multiqubit quantum states employed in the Grover algorithm, by following its dynamics at each step of the computation. We show that genuine multipartite entanglement is always present. Remarkably, the dynamics of any type of entanglement as well as of genuine multipartite entanglement is independent of the number $n$ of qubits for large $n$ , thus exhibiting a scale invariance property. We compare this result with the entanglement dynamics induced by a fixed-point quantum search algorithm. We also investigate criteria for efficient simulatability in the context of Grover's algorithm.We calculate the amount of entanglement of the multiqubit quantum states employed in the Grover algorithm, by following its dynamics at each step of the computation. We show that genuine multipartite entanglement is always present. Remarkably, the dynamics of any type of entanglement as well as of genuine multipartite entanglement is independent of the number $n$ of qubits for large $n$, thus exhibiting a scale invariance property. We compare this result with the entanglement dynamics induced by a fixed-point quantum search algorithm. We also investigate criteria for efficient simulatability in the context of Grover's algorithm.

arXiv:1205.3000Physical Review AFeb 21, 201336 citations

Grover’s Algorithm and Its Generalization

Renato Portugal

Springer eBooksJan 1, 20130 citations

Speedup of Grover’s search algorithm and closed timelike curves

Ki Hyuk Yee, Jeongho Bang, Paul M. Alsing +2 more

Abstract The quadratic reduction of query complexity of Grover’s search algorithm (GA), while significant, would not be enough to enjoy exponentially fast data searching in large-scale quantum computation. One of the ways to enhance the speedup in the framework of Grover’s algorithm is to employ a novel quantum operation, i.e., inversion against an unknown state; however, this is not possible at least in quantum theory. We thus extend the Grover algorithm assisted by closed timelike curves (CTCs), in which the unknown-state inversion is achievable by combining the superposition of two unknown states with cloning. We dubbed this refined algorithm CTC-assisted Grover algorithm (CTC-GA). We show that the CTC-GA can vastly reduce the query complexity compared to the original algorithm; remarkably, from polynomial to poly-logarithmic. These results will provide a broader intuition for exponential quantum speedup of data searching problems.Abstract The quadratic reduction of query complexity of Grover’s search algorithm (GA), while significant, would not be enough to enjoy exponentially fast data searching in large-scale quantum computation. One of the ways to enhance the speedup in the framework of Grover’s algorithm is to employ a novel quantum operation, i.e., inversion against an unknown state; however, this is not possible at least in quantum theory. We thus extend the Grover algorithm assisted by closed timelike curves (CTCs), in which the unknown-state inversion is achievable by combining the superposition of two unknown states with cloning. We dubbed this refined algorithm CTC-assisted Grover algorithm (CTC-GA). We show that the CTC-GA can vastly reduce the query complexity compared to the original algorithm; remarkably, from polynomial to poly-logarithmic. These results will provide a broader intuition for exponential quantum speedup of data searching problems.

Quantum Science and TechnologyAug 12, 20204 citations

Grover's Algorithm

Ahcène Bounceur, Mohammad Ali A. Hammoudeh, Bamidele Adebisi +1 more

This chapter examines Grover's algorithm, a quantum algorithm known for its efficacy in searching unsorted databases. Starting with a theoretical exposition complemented by geometric explanations and exemplified through iterative demonstrations, readers gain a clear understanding of the algorithmic principles at play. Then, this chapter examines the quantum domain, the exposition encompasses a comprehensive breakdown of the quantum circuit's construction, describing the specific roles of each constituent in facilitating algorithmic execution. Grover's algorithm is known for its remarkable ability to significantly reduce the computational resources required for executing the brute-force search problem. The chapter concludes with practical showcases utilising the Qiskit programming framework, thereby demonstrating the algorithm's scalability and practical utility across varying problem dimensions.This chapter examines Grover's algorithm, a quantum algorithm known for its efficacy in searching unsorted databases. Starting with a theoretical exposition complemented by geometric explanations and exemplified through iterative demonstrations, readers gain a clear understanding of the algorithmic principles at play. Then, this chapter examines the quantum domain, the exposition encompasses a comprehensive breakdown of the quantum circuit's construction, describing the specific roles of each constituent in facilitating algorithmic execution. Grover's algorithm is known for its remarkable ability to significantly reduce the computational resources required for executing the brute-force search problem. The chapter concludes with practical showcases utilising the Qiskit programming framework, thereby demonstrating the algorithm's scalability and practical utility across varying problem dimensions.

CRC Press eBooksDec 9, 20243 citations

Grover’s Algorithm and Its Generalization

Renato Portugal

Quantum science and technologyJan 1, 20180 citations

n

of qubits for large

n

, thus exhibiting a scale invariance property. We compare this result with the entanglement dynamics induced by a fixed-point quantum search algorithm. We also investigate criteria for efficient simulatability in the context of Grover's algorithm.