If $2$ qubits together provide the states 00, 01, 11 or 10 simultaneously which represent $4$ probabilities in total, how many probabilities do $N$ qubits represent? Does the formula for this somehow express quadratic/exponential speed-up?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Does this answer your question? Is quantum parallel search impossible? $\endgroup$– Sanchayan DuttaCommented Dec 7, 2019 at 9:43
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
$N$ qubits have $2^N$ basis states, and $2^N$ probabilities (to be in each of basis states).
The question "does the number of probabilities express the exponential speed-up ?" does not make sense to me.
-
$\begingroup$ the exponent of your base 2 is the number of qubits, $N$ rather than $1/N$. this is what got me thinking that it somehow conveys exponential (whole number for an exponent) rather than quadratic (fractional number for an exponent) speed-up $\endgroup$ Commented Dec 8, 2019 at 2:29
$\begingroup$
$\endgroup$
Sometimes, mainly in popular articles and books, it is stated that $n$ qubits can be in all $2^n$ possible zero-one combinations simultaneously (the superposition of these combinations) and any calculation on this register is done with all these combinations. This is used as an explanation for speed-up brings by a quantum computer. However, this is misunderstanding. If you want to use this explanation, you have to add that it is necessary to repeat an algorithm run many times and as a result you lose some of the speed-up. But this is still not precise explanation. You have to use laws of a quantum mechanics to explain this preciselly. Unfortunately there is no precise and at the same time "popular" explanation.
Additionlly, the reason behind the speed-up is different for different algorithms. The scale of the speed-up is also different. It is for example quadratic for Monte Carlo simulation or database search (Grover algorithm) and exponential for solving linear equations (HHL algorithm) or integer factorization (Shor algorithm). Moreover, there are algorithms bringing no speed-up in comparison with a classical computer (e.g. binary function parity evaluation).
Note: to be precise about HHL algorithm, it brings exponential speed-up only in case we are looking for value $x^TMx$ for some operator $M$ and $x$ is a solution of $Ax=b$.
answered Dec 7, 2019 at 7:54
$\begingroup$
$\endgroup$
1
The speed up is not expressed by the exponentially many basis states that a quantum system can be in.
The speedup comes from being able to recombine the probability amplitudes associated to the these basis states so that a measurement can output the correct result of the computation with sufficiently high probability.
If the exponentially many basis states accessible alone would make up for the speedup then any algorithm would be speedup by a quantum computer. And that's not the case.
-
$\begingroup$ so how does the recombination of probability amplitudes impact the formula of finding number of probabilities based on number of qubits? is there another property from quantum mechanics besides the number of qubits that can (or contributes to how to) gauge the number of probabilities? $\endgroup$ Commented Dec 8, 2019 at 2:34