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/9803064

Quantum Computers Speed Up Classical with Probability Zero

Yuri Ozhigov

Published Mar 24, 1998• 13 citations
arXivHTMLPDF

Abstract

Let $f$ denote length preserving function on words. A classical algorithm can be considered as $T$ iterated applications of black box representing $f$, beginning with input word $x$ of length $n$. It is proved that if $T=O(2^{n/(7+e)}), e >0$, and $f$ is chosen randomly then with probability 1 every quantum computer requires not less than $T$ evaluations of $f$ to obtain the result of classical computation. It means that the set of classical algorithms admitting quantum speeding up has probability measure zero. The second result is that for arbitrary classical time complexity $T$ and $f$ chosen randomly with probability 1 every quantum simulation of classical computation requires at least $Ω(\sqrt {T})$ evaluations of $f$.

DOI
10.48550/arxiv.quant-ph/9803064

Related papers

Quantum Computer Can Not Speed Up Iterated Applications of a Black Box

Yuri Ozhigov

Let a classical algorithm be determined by sequential applications of a black box performing one step of this algorithm. If we consider this black box as an oracle which gives a value F(a) for any query a, we can compute T sequential applications of F on a classical computer relative to this oracle in time T. It is proved that if T=O(2^{n/7}), where n is the length of input, then the result of T sequential applications of F can not be computed on quantum computer with oracle for F for all possible F faster than in time Ω(T). This means that there is no general method of quantum speeding up of classical algorithms provided in such a general method a classical algorithm is regarded as iterated applications of a given black box. For an arbitrary time complexity T a lower bound for the time of quantum simulation was found to be Ω(T^{1/2}).

arXiv:quant-ph/9712051•Dec 22, 1997•10 citations

On the Relation Between Quantum Computational Speedup and Retrocausality

Giuseppe Castagnoli

We investigate the reason for the quantum speedup (quantum algorithms require fewer computation steps than their classical counterparts). We extend the representation of the quantum algorithm to the process of setting the problem, namely choosing the function computed by the black box. The initial measurement selects a setting at random, Bob (the problem setter) unitarily changes it into the desired one. With reference to the observer dependent quantum states of relational quantum mechanics, this representation is with respect to Bob and any external observer, it cannot be with respect to Alice (the problem solver). It would tell her the function computed by the black box, which to her should be hidden. To Alice, the projection of the quantum state due to the initial measurement is retarded at the end of her problem solving action, so that the algorithm input state remains one of complete ignorance of the setting. By black box computations, she unitarily sends it into the output state that, for each possible setting, encodes the corresponding solution, acquired by the final measurement. Mathematically, we can ascribe to the final measurement the selection of any fraction R of the random outcome of the initial measurement. This projects the input state to Alice on one of lower entropy where she knows the corresponding fraction of the problem setting. Given the appropriate value of R, the quantum algorithm is a sum over classical histories in each of which Alice, knowing in advance one of the R-th parts of the setting, performs the black box computations still required to identify the solution. Given a quantum algorithm, this retrocausality model provides the value of R that explains its speed up; in the major quantum algorithms, R is 1/2 or slightly above it. Conversely, given the problem, R=1/2 always yields the order of magnitude of the number of black box computations required to solve it in an optimal quantum way. Quanta 2016; 5: 34–52.

Quanta•Jan 10, 2016•8 citations

Quantum Computational Complexity Theory and Lower Bounds

Phillip Kaye, Raymond Laflamme, Michele Mosca

We have seen in the previous chapters that quantum computers seem to be more powerful than classical computers for certain problems. There are limits on the power of quantum computers, however. Since a classical computer can simulate a quantum computer, a quantum computer can only compute the same set of functions that a classical computer can. The advantage of using a quantum computer is that the amount of resources needed by a quantum algorithm might be much less than what is needed by the best classical algorithm. In Section 9.1 we briefly define some classical and quantum complexity classes and give some relationships between them. Most of the interesting questions relating classical and quantum complexity classes remain open. For example, we do not yet know if a quantum computer is capable of efficiently solving an NP-complete problem (defined later). One can prove upper bounds on the difficulty of a problem by providing an algorithm that solves that problem, and proving that it will work within in a given running time. But how does one prove a lower bound on the computational complexity of a problem? For example, if we wish to find the product of two n-bit numbers, computing the answer requires outputting roughly 2n bits and that requires Ω(n) steps (in any computing model with finite-sized gates). The best-known upper bound for integer multiplication is O(n log n log log n) steps. It has proved extremely difficult to derive non-trivial lower bounds on the computational complexity of a problem. Most of the known non-trivial lower bounds are in the ‘black-box’ model (for both classical and quantum computing), where we only query the input via a ‘black-box’ of a specific form. We discuss the black-box model in more detail in Section 9.2. We then sketch several approaches for proving black-box lower bounds. The first technique has been called the ‘hybrid method’ and was used to prove that quantum searching requires Ω(√n) queries to succeed with constant probability. The second technique is called the ‘polynomial method’. We then describe a technique based on ‘block sensitivity’, and conclude with a technique known as the ‘adversary method’.

Oxford University Press eBooks•Nov 16, 2006•0 citations

Explaining the mechanism of the quantum speed-up in time-symmetric quantum mechanics

Giuseppe Castagnoli

Bob chooses a function from a set of functions and gives Alice the black box that computes it. Alice is to find a characteristic of the function through function evaluations. In the quantum case, the number of function evaluations can be smaller than the minimum classically possible. The fundamental reason for this violation of a classical limit is not known. We trace it back to a disambiguation of the principle that measuring an observable determines one of its eigenvalues. Representing Bob's choice of the label of the function as the unitary transformation of a random quantum measurement outcome shows that: (i) finding the characteristic of the function on the part of Alice is a by-product of reconstructing Bob's choice and (ii) because of the quantum correlation between choice and reconstruction, one cannot tell whether Bob's choice is determined by the action of Bob (initial measurement and successive unitary transformation) or that of Alice (further unitary transformation and final measurement). Postulating that the determination shares evenly between the two actions, in a uniform superposition of all the possible ways of sharing, implies that quantum algorithms are superpositions of histories in each of which Alice knows in advance one of the possible halves of Bob's choice. Performing, in each history, only the function evaluations required to classically reconstruct Bob's choice given the advanced knowledge of half of it yields the quantum speed-up. In all the cases examined, this goes along with interleaving function evaluations with non-computational unitary transformations that each time maximize the amount of information about Bob's choice acquired by Alice with function evaluation.

arXiv:1107.0934•Jul 5, 2011•4 citations

Classical Computation in the Quantum World

Jiachen Huang

Quantum computation is by far the most powerful computational model allowed by the laws of physics. By carefully manipulating microscopic systems governed by quantum mechanics, one can efficiently solve computational problems that may be classically intractable; on the contrary, such speed-ups are rarely possible without the help of classical computation, since most quantum algorithms heavily rely on subroutines that are purely classical. A better understanding of the relationship between classical and quantum computation is indispensable, in particular in an era where the first quantum device exceeding classical computational power is within reach. In the first part of the thesis, we study some differences between classical and quantum computation. We first show that quantum cryptographic hashing is maximally resilient against classical leakage, a property beyond reach for any classical hash function. Next, we consider the limitation of strong (amplitude-wise) simulation of quantum computation. We prove an unconditional and explicit complexity lower bound for a category of simulations called monotone strong simulation and further prove conditional complexity lower bounds for general strong simulation techniques. Both results indicate that strong simulation is fundamentally unscalable. In the second part of the thesis, we propose classical algorithms that facilitate quantum computing. We propose a new classical algorithm for the synthesis of a quantum algorithm paradigm called quantum signal processing. Empirically, our algorithm demonstrates numerical stability and acceleration of more than one magnitude compared to state-of-the-art algorithms. Finally, we propose a randomized algorithm for transversally switching between arbitrary stabilizer quantum error-correcting codes. It has the property of preserving the code distance and thus might prove useful for designing fault-tolerant code-switching schemes.

•Jan 1, 2019•0 citations

Limit on the Speed of Quantum Computation in Determining Parity

Edward Farhi, Jeffrey Goldstone, Sam Gutmann +1 more

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.

arXiv:quant-ph/9802045•Physical Review Letters•Dec 14, 1998•181 citations
Let fff denote length preserving function on words. A classical algorithm can be considered as TTT iterated applications of black box representing fff, beginning with input word xxx of length nnn. It is proved that if T=O(2n/(7+e)),e>0T=O(2^{n/(7+e)}), e >0T=O(2n/(7+e)),e>0, and fff is chosen randomly then with probability 1 every quantum computer requires not less than TTT evaluations of fff to obtain the result of classical computation. It means that the set of classical algorithms admitting quantum speeding up has probability measure zero. The second result is that for arbitrary classical time complexity TTT and fff chosen randomly with probability 1 every quantum simulation of classical computation requires at least Ω(T)Ω(\sqrt {T})Ω(T​) evaluations of fff.
Let a classical algorithm be determined by sequential applications of a black box performing one step of this algorithm. If we consider this black box as an oracle which gives a value F(a) for any query a, we can compute T sequential applications of F on a classical computer relative to this oracle in time T. It is proved that if T=O(2^{n/7}), where n is the length of input, then the result of T sequential applications of F can not be computed on quantum computer with oracle for F for all possible F faster than in time Ω(T). This means that there is no general method of quantum speeding up of classical algorithms provided in such a general method a classical algorithm is regarded as iterated applications of a given black box. For an arbitrary time complexity T a lower bound for the time of quantum simulation was found to be Ω(T^{1/2}).
We investigate the reason for the quantum speedup (quantum algorithms require fewer computation steps than their classical counterparts). We extend the representation of the quantum algorithm to the process of setting the problem, namely choosing the function computed by the black box. The initial measurement selects a setting at random, Bob (the problem setter) unitarily changes it into the desired one. With reference to the observer dependent quantum states of relational quantum mechanics, this representation is with respect to Bob and any external observer, it cannot be with respect to Alice (the problem solver). It would tell her the function computed by the black box, which to her should be hidden. To Alice, the projection of the quantum state due to the initial measurement is retarded at the end of her problem solving action, so that the algorithm input state remains one of complete ignorance of the setting. By black box computations, she unitarily sends it into the output state that, for each possible setting, encodes the corresponding solution, acquired by the final measurement. Mathematically, we can ascribe to the final measurement the selection of any fraction R of the random outcome of the initial measurement. This projects the input state to Alice on one of lower entropy where she knows the corresponding fraction of the problem setting. Given the appropriate value of R, the quantum algorithm is a sum over classical histories in each of which Alice, knowing in advance one of the R-th parts of the setting, performs the black box computations still required to identify the solution. Given a quantum algorithm, this retrocausality model provides the value of R that explains its speed up; in the major quantum algorithms, R is 1/2 or slightly above it. Conversely, given the problem, R=1/2 always yields the order of magnitude of the number of black box computations required to solve it in an optimal quantum way. Quanta 2016; 5: 34–52.
We have seen in the previous chapters that quantum computers seem to be more powerful than classical computers for certain problems. There are limits on the power of quantum computers, however. Since a classical computer can simulate a quantum computer, a quantum computer can only compute the same set of functions that a classical computer can. The advantage of using a quantum computer is that the amount of resources needed by a quantum algorithm might be much less than what is needed by the best classical algorithm. In Section 9.1 we briefly define some classical and quantum complexity classes and give some relationships between them. Most of the interesting questions relating classical and quantum complexity classes remain open. For example, we do not yet know if a quantum computer is capable of efficiently solving an NP-complete problem (defined later). One can prove upper bounds on the difficulty of a problem by providing an algorithm that solves that problem, and proving that it will work within in a given running time. But how does one prove a lower bound on the computational complexity of a problem? For example, if we wish to find the product of two n-bit numbers, computing the answer requires outputting roughly 2n bits and that requires Ω(n) steps (in any computing model with finite-sized gates). The best-known upper bound for integer multiplication is O(n log n log log n) steps. It has proved extremely difficult to derive non-trivial lower bounds on the computational complexity of a problem. Most of the known non-trivial lower bounds are in the ‘black-box’ model (for both classical and quantum computing), where we only query the input via a ‘black-box’ of a specific form. We discuss the black-box model in more detail in Section 9.2. We then sketch several approaches for proving black-box lower bounds. The first technique has been called the ‘hybrid method’ and was used to prove that quantum searching requires Ω(√n) queries to succeed with constant probability. The second technique is called the ‘polynomial method’. We then describe a technique based on ‘block sensitivity’, and conclude with a technique known as the ‘adversary method’.
Bob chooses a function from a set of functions and gives Alice the black box that computes it. Alice is to find a characteristic of the function through function evaluations. In the quantum case, the number of function evaluations can be smaller than the minimum classically possible. The fundamental reason for this violation of a classical limit is not known. We trace it back to a disambiguation of the principle that measuring an observable determines one of its eigenvalues. Representing Bob's choice of the label of the function as the unitary transformation of a random quantum measurement outcome shows that: (i) finding the characteristic of the function on the part of Alice is a by-product of reconstructing Bob's choice and (ii) because of the quantum correlation between choice and reconstruction, one cannot tell whether Bob's choice is determined by the action of Bob (initial measurement and successive unitary transformation) or that of Alice (further unitary transformation and final measurement). Postulating that the determination shares evenly between the two actions, in a uniform superposition of all the possible ways of sharing, implies that quantum algorithms are superpositions of histories in each of which Alice knows in advance one of the possible halves of Bob's choice. Performing, in each history, only the function evaluations required to classically reconstruct Bob's choice given the advanced knowledge of half of it yields the quantum speed-up. In all the cases examined, this goes along with interleaving function evaluations with non-computational unitary transformations that each time maximize the amount of information about Bob's choice acquired by Alice with function evaluation.
Quantum computation is by far the most powerful computational model allowed by the laws of physics. By carefully manipulating microscopic systems governed by quantum mechanics, one can efficiently solve computational problems that may be classically intractable; on the contrary, such speed-ups are rarely possible without the help of classical computation, since most quantum algorithms heavily rely on subroutines that are purely classical. A better understanding of the relationship between classical and quantum computation is indispensable, in particular in an era where the first quantum device exceeding classical computational power is within reach. In the first part of the thesis, we study some differences between classical and quantum computation. We first show that quantum cryptographic hashing is maximally resilient against classical leakage, a property beyond reach for any classical hash function. Next, we consider the limitation of strong (amplitude-wise) simulation of quantum computation. We prove an unconditional and explicit complexity lower bound for a category of simulations called monotone strong simulation and further prove conditional complexity lower bounds for general strong simulation techniques. Both results indicate that strong simulation is fundamentally unscalable. In the second part of the thesis, we propose classical algorithms that facilitate quantum computing. We propose a new classical algorithm for the synthesis of a quantum algorithm paradigm called quantum signal processing. Empirically, our algorithm demonstrates numerical stability and acceleration of more than one magnitude compared to state-of-the-art algorithms. Finally, we propose a randomized algorithm for transversally switching between arbitrary stabilizer quantum error-correcting codes. It has the property of preserving the code distance and thus might prove useful for designing fault-tolerant code-switching schemes.
Consider a function fff which is defined on the integers from 1 to NNN and takes the values $\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.