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

arXiv:1211.3405

The Measurement Based Quantum Computing Search Algorithm is Faster than Grover's Algorithm

A. Matthew Smith, Paul M. Alsing

Published Nov 14, 2012• 2 citations
arXivHTMLPDF

Abstract

We find that the Measurement Based Quantum Computing (MBQC) search algorithm on an unsorted list is not the same as Grover's search algorithm (GSA).
DOI
10.48550/arxiv.1211.3405

Related papers

Grover's search algorithm and the quantum measurement problem

Manoj K. Samal, Partha Ghose

It is suggested that the individual outcomes of a measurement process can be understood within standard quantum mechanics in terms of the measuring apparatus, treated as a quantum computer, executing Grover's search algorithm.

arXiv:quant-ph/0202176•Feb 28, 2002•2 citations

Finding Matches between Two Databases on a Quantum Computer

Mark Heiligman

Given two unsorted lists each of length N that have a single common entry, a quantum computer can find that matching element with a work factor of $O(N^{3/4}\log N)$ (measured in quantum memory accesses and accesses to each list). The amount of quantum memory required is $O(N^{1/2})$. The quantum algorithm that accomplishes this consists of an inner Grover search combined with a partial sort all sitting inside of an outer Grover search.

arXiv:quant-ph/0006136•Jun 30, 2000•14 citations

Programming non-trivial algorithms in the measurement-based quantum computation model

Paul M. Alsing, A. Matthew Smith, Michael L. Fanto +2 more

We provide a set of prescriptions for implementing a quantum circuit model algorithm as measurement based quantum computing (MBQC) algorithm via a large cluster state. As means of illustration we draw upon our numerical modeling experience to describe a large graph state capable of searching a logical 8 element list (a non-trivial version of Grover's algorithm with feedforward). We develop several prescriptions based on analytic evaluation of cluster states and graph state equations which can be generalized into any circuit model operations. Such a resulting cluster state will be able to carry out the desired operation with appropriate measurements and feed forward error correction. We also discuss the physical implementation and the analysis of the principal 3-qubit entangling gate (Tooli) required for a non-trivial feedforward realization of an 8-element Grover search algorithm.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Oct 13, 2014•1 citation

The quadratic speedup in Grover's search algorithm from the entanglement perspective

Pranaw Rungta

arXiv:0707.1410•Physics Letters A•May 31, 2009•21 citations

Simulating a Quantum Computer : Grover's Search Algorithm with Error Correction

Martin Sjöborg, Hanna Linn

Classical simulations of quantum computers give us an insight into various things such as what quantum algorithms can achieve, whether it is possible to verify that they function as postulated, the difficulties that have to be overcome before quantum computers can be realized, as well as how we can handle these difficulties. We build a Python library to simulate a quantum computer that can perform all quantum algorithms by defining an universal gate set, from which all quantum gates – and thereby all circuits – can be constructed. We implement two algorithms that both highlight two important aspects of quantum computing: Grover’s quantum search algorithm, which demonstrates the efficiency of quantum algorithms and their superiority over their classical counterparts by searching an unsorted list quadratically faster; and an error correcting code, the Shor code, which highlights the cost of correcting the possible errors in a quantum computer.We test the rigidity of Grover’s algorithm by introducing errors without correction, and find that the algorithm shows resilience to smaller 1-qubit Pauli errors, but looses its efficiency under larger errors and thus the need for Pauli error correction arise.

•Jan 1, 2018•0 citations

Quantum mechanical searching

Lov K. Grover

It has recently been shown that the searching speed of computers based on quantum mechanics is far superior to their classical counterparts.

IEEE Congress on Evolutionary Computation (CEC)•Jan 20, 2003•26 citations
Given two unsorted lists each of length N that have a single common entry, a quantum computer can find that matching element with a work factor of O(N3/4log⁡N)O(N^{3/4}\log N)O(N3/4logN) (measured in quantum memory accesses and accesses to each list). The amount of quantum memory required is O(N1/2)O(N^{1/2})O(N1/2). The quantum algorithm that accomplishes this consists of an inner Grover search combined with a partial sort all sitting inside of an outer Grover search.
We provide a set of prescriptions for implementing a quantum circuit model algorithm as measurement based quantum computing (MBQC) algorithm via a large cluster state. As means of illustration we draw upon our numerical modeling experience to describe a large graph state capable of searching a logical 8 element list (a non-trivial version of Grover's algorithm with feedforward). We develop several prescriptions based on analytic evaluation of cluster states and graph state equations which can be generalized into any circuit model operations. Such a resulting cluster state will be able to carry out the desired operation with appropriate measurements and feed forward error correction. We also discuss the physical implementation and the analysis of the principal 3-qubit entangling gate (Tooli) required for a non-trivial feedforward realization of an 8-element Grover search algorithm.
Classical simulations of quantum computers give us an insight into various things such as what quantum algorithms can achieve, whether it is possible to verify that they function as postulated, the difficulties that have to be overcome before quantum computers can be realized, as well as how we can handle these difficulties. We build a Python library to simulate a quantum computer that can perform all quantum algorithms by defining an universal gate set, from which all quantum gates – and thereby all circuits – can be constructed. We implement two algorithms that both highlight two important aspects of quantum computing: Grover’s quantum search algorithm, which demonstrates the efficiency of quantum algorithms and their superiority over their classical counterparts by searching an unsorted list quadratically faster; and an error correcting code, the Shor code, which highlights the cost of correcting the possible errors in a quantum computer.We test the rigidity of Grover’s algorithm by introducing errors without correction, and find that the algorithm shows resilience to smaller 1-qubit Pauli errors, but looses its efficiency under larger errors and thus the need for Pauli error correction arise.