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:quant-ph/9802045 · Physical Review Letters

Limit on the Speed of Quantum Computation in Determining Parity

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sipser

Published Dec 14, 1998• 181 citations
arXivHTMLPDF

Abstract

Consider a function $f$ which is defined on the integers from 1 to $N$ and takes the values $\ensuremath{-}1$ and $+1$. The parity of $f$ is the product over all $x$ from 1 to $N$ of $f(x)$. With no further information about $f$, to classically determine the parity of $f$ requires $N$ calls of the function $f$. We show that any quantum algorithm capable of determining the parity of $f$ contains at least $N/2$ applications of the unitary operator which evaluates $f$. Thus, for this problem, quantum computers cannot outperform classical computers.

DOI
10.1103/physrevlett.81.5442

Related papers

Quantum parity algorithms as oracle calls, and application in Grover Database search

Magdi Z. Rashad

This paper discusses the determination of the parity of a string of N binary digits, the well-known problem in classical as well as quantum information processing.It can be formulated as an oracle problem.It has been established that quantum algorithms require at least N /2 oracle calls.We present an algorithm that reaches this lower bound and is also optimal in terms of additional gate operations required.

Advanced Computing An International Journal•Mar 31, 2012•0 citations

Quantum circuits: power and limitations

Steven Homer, Debajyoti Bera

Quantum computation was proposed as an alternate computing process in the late-20th century, when classical computing models faced limitation in solving quantum mechanical problems. Major breakthroughs came in the 1990s, when quantum algorithms for integer factoring and black-box searching were invented that are faster than the best classical algorithms known even today. In this thesis, we look at quantum circuits with limited depth and size and analyse their power and limitations. Computer Science is about the study of computational problems, many of which are motivated by real-world applications. We are interested as much in an actual method to solve a problem as in its unsolvability. In computational complexity theory we separate out the actual problem from the computing apparatus (e.g. a Turing machine, an AND-OR circuit) and analyse the hardness of the computation, due both to the intrinsic complexity of the problem and to the underlying model. In this thesis, we consider quantum circuits built with a universal set of gates and show that non-constant depth is required to compute a particular function (parity) and other similar functions. The parity function, extensively studied previously, was shown to take non-constant depth for classical circuits too, thus providing an evidence of an inherent hardness in the function itself. On the other hand we show that the quantum circuit model is rich enough to build a universal circuit (one circuit that can simulate all circuits) that has roughly the same depth or size as the simulated circuit. We also consider a fault model in which some of the inputs to a gate might not be connected to the gate's output. We ask if we can detect the faulty inputs by testing the gate on different inputs. Our goal is to minimise the number of tests. We show that this is very hard for general gates but for certain gates it can be provably easier to detect faulty inputs. We even show that quantum algorithms can provably outperform classical algorithms for these gates. These results give us a sense of wherein lies the power of quantum computation and quantum circuits in particular.

•Jan 1, 2010•3 citations

Quantum and classical parallelism in parity algorithms for ensemble quantum computers

Ralf Stadelhofer, Dieter Suter, Wolfgang Banzhaf

The determination of the parity of a string of $N$ binary digits is a well-known problem in classical as well as quantum information processing, which can be formulated as an oracle problem. It has been established that quantum algorithms require at least $N∕2$ oracle calls. We present an algorithm that reaches this lower bound and is also optimal in terms of additional gate operations required. We discuss its application to pure and mixed states. Since it can be applied directly to thermal states, it does not suffer from signal loss associated with pseudo-pure-state preparation. For ensemble quantum computers, the number of oracle calls can be further reduced by a factor ${2}^{k}$, with $k∊{1,2,\dots{},{\mathrm{log}}_{2}(N∕2)}$, provided the signal-to-noise ratio is sufficiently high. This additional speed-up is linked to (classical) parallelism of the ensemble quantum computer. Experimental realizations are demonstrated on a liquid-state NMR quantum computer.

Physical Review A•Mar 28, 2005•20 citations

Introduction to Quantum Algorithms

Peter W. Shor

These notes discuss the quantum algorithms we know of that can solve problems significantly faster than the corresponding classical algorithms. So far, we have only discovered a few techniques which can produce speed up versus classical algorithms. It is not clear yet whether the reason for this is that we do not have enough intuition to discover more techniques, or that there are only a few problems for which quantum computers can significantly speed up the solution.

arXiv:quant-ph/0005003•Apr 29, 2000•78 citations

On the Power of Quantum Computation: Oracles

Niklas Johansson

Quantum computation solve some computational problems faster than the best-known alternative in classical computation. The evidence for this consists of examples where a quantum algorithm outperfor ...

•Jan 1, 2018•0 citations

Computational speed-up with a single qudit

Z. Gedik, I. A. Silva, Barış Çakmak +5 more

Quantum algorithms are known for providing more efficient solutions to certain computational tasks than any corresponding classical algorithm. Here we show that a single qudit is sufficient to implement an oracle based quantum algorithm, which can solve a black-box problem faster than any classical algorithm. For 2d permutation functions defined on a set of d elements, deciding whether a given permutation is even or odd, requires evaluation of the function for at least two elements. We demonstrate that a quantum circuit with a single qudit can determine the parity of the permutation with only one evaluation of the function. Our algorithm provides an example for quantum computation without entanglement since it makes use of the pure state of a qudit. We also present an experimental realization of the proposed quantum algorithm with a quadrupolar nuclear magnetic resonance using a single four-level quantum system, i.e., a ququart.

•Oct 8, 2015•31 citations
Consider a function fff which is defined on the integers from 1 to NNN and takes the values \ensuremath−1\ensuremath{-}1\ensuremath−1 and +1+1+1. The parity of fff is the product over all xxx from 1 to NNN of f(x)f(x)f(x). With no further information about fff, to classically determine the parity of fff requires NNN calls of the function fff. We show that any quantum algorithm capable of determining the parity of fff contains at least N/2N/2N/2 applications of the unitary operator which evaluates fff. Thus, for this problem, quantum computers cannot outperform classical computers.
Quantum computation was proposed as an alternate computing process in the late-20th century, when classical computing models faced limitation in solving quantum mechanical problems. Major breakthroughs came in the 1990s, when quantum algorithms for integer factoring and black-box searching were invented that are faster than the best classical algorithms known even today. In this thesis, we look at quantum circuits with limited depth and size and analyse their power and limitations. Computer Science is about the study of computational problems, many of which are motivated by real-world applications. We are interested as much in an actual method to solve a problem as in its unsolvability. In computational complexity theory we separate out the actual problem from the computing apparatus (e.g. a Turing machine, an AND-OR circuit) and analyse the hardness of the computation, due both to the intrinsic complexity of the problem and to the underlying model. In this thesis, we consider quantum circuits built with a universal set of gates and show that non-constant depth is required to compute a particular function (parity) and other similar functions. The parity function, extensively studied previously, was shown to take non-constant depth for classical circuits too, thus providing an evidence of an inherent hardness in the function itself. On the other hand we show that the quantum circuit model is rich enough to build a universal circuit (one circuit that can simulate all circuits) that has roughly the same depth or size as the simulated circuit. We also consider a fault model in which some of the inputs to a gate might not be connected to the gate's output. We ask if we can detect the faulty inputs by testing the gate on different inputs. Our goal is to minimise the number of tests. We show that this is very hard for general gates but for certain gates it can be provably easier to detect faulty inputs. We even show that quantum algorithms can provably outperform classical algorithms for these gates. These results give us a sense of wherein lies the power of quantum computation and quantum circuits in particular.
The determination of the parity of a string of NNN binary digits is a well-known problem in classical as well as quantum information processing, which can be formulated as an oracle problem. It has been established that quantum algorithms require at least N∕2N∕2N∕2 oracle calls. We present an algorithm that reaches this lower bound and is also optimal in terms of additional gate operations required. We discuss its application to pure and mixed states. Since it can be applied directly to thermal states, it does not suffer from signal loss associated with pseudo-pure-state preparation. For ensemble quantum computers, the number of oracle calls can be further reduced by a factor 2k{2}^{k}2k, with k∊1,2,…,log2(N∕2)k∊{1,2,\dots{},{\mathrm{log}}_{2}(N∕2)}k∊1,2,…,log2​(N∕2), provided the signal-to-noise ratio is sufficiently high. This additional speed-up is linked to (classical) parallelism of the ensemble quantum computer. Experimental realizations are demonstrated on a liquid-state NMR quantum computer.
Quantum algorithms are known for providing more efficient solutions to certain computational tasks than any corresponding classical algorithm. Here we show that a single qudit is sufficient to implement an oracle based quantum algorithm, which can solve a black-box problem faster than any classical algorithm. For 2d permutation functions defined on a set of d elements, deciding whether a given permutation is even or odd, requires evaluation of the function for at least two elements. We demonstrate that a quantum circuit with a single qudit can determine the parity of the permutation with only one evaluation of the function. Our algorithm provides an example for quantum computation without entanglement since it makes use of the pure state of a qudit. We also present an experimental realization of the proposed quantum algorithm with a quadrupolar nuclear magnetic resonance using a single four-level quantum system, i.e., a ququart.