What does one mean by saying that classical bits perform operations at the scale of $2n$ and quantum computers perform operations at the scale of $2^n$? In both cases, $n$ = Number of bits/qubits.
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ Do you have a reference for this? Or maybe more context? $\endgroup$– M. SternCommented Mar 26, 2018 at 14:35
-
$\begingroup$ How does classical scale with $2n$? Do you mean that the state size doubles with every bit added? And where does the '2^n' come from? IIRC, quantum state is analog, so the state is essentially uncountably large (even for a single qubit) although the number of different measures eventually are finite due to finite precision $\endgroup$– Discrete lizardCommented Mar 26, 2018 at 15:08
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
I'm not sure it really is true to make such a claim, even though it is one that is often seen. Even so, this statement is common because it does point towards a difference between classical computers and quantum ones.
Classical computation is essentially a process that takes a single input bit string and keeps transforming it until you get a single output bit string. You can think of the whole process as only ever having one bit string in the computer at once.
The same is true for quantum computers, except that you need to replace 'bit string' with 'state of many qubits'. So how do bit strings compare with multi qubit states? To find out, we can look at how classical computers can simulate quantum ones.
One way to represent states of $n$ qubits in a classical computer is to think of them as superpositions of all possible $n$-bit strings. Then you can have a big array, which stores the corresponding amplitude for every $n$-bit string. Since there are $2^n$ $n$-bit strings, this will take an exponentially large amount of memory. This is often not the most efficient method of representing quantum states, but there are cases when it is no worse than any other.
So if we need to simulate any possible process for $n$ qubits with bits, we know that it will incur this kind of overhead. If we use this to draw a comparison between qubits and bits, we could say that an exponentially large number of qubits are required to match the power of $n$ bits. But the same would not be true for all possible computational tasks.
answered Mar 26, 2018 at 12:33
-
$\begingroup$ Would it be correct to say that a quantum computer is essentially analog, not digital? $\endgroup$ Commented Mar 26, 2018 at 15:18
-
$\begingroup$ That's not really true either. You are simulating by storing $2^n$ amplitudes (at some precision), but you won't have access to them at the end. Eventually you will do a digital readout. Analog seems to imply that everything is real or complex valued throughout and you can read that out too. $\endgroup$– AHusainCommented Mar 26, 2018 at 21:46
-
$\begingroup$ @Discretelizard There are certainly analog aspects to quantum computation. But there are digital aspects too. Wave-particle duality essentially looks like analog-digital duality when looked at from a computational perspective. $\endgroup$ Commented Mar 26, 2018 at 22:29
$\begingroup$
$\endgroup$
1
The reason is because of the superposition. It allows you to perform operations and won the speed up. For example, if you have a just one qubit you will have the following because of the superposition:
$$\alpha_0\lvert0\rangle + \alpha_1\lvert1\rangle$$
You can see that you have already $2$ basis for one qubit. If you have two qubits you will have $4$ basis for your system and go on. I will put the $2$ qubit but as a combination of tensor product of the previous basis and we will have:
$$\lvert0\rangle ⊗ \lvert0\rangle, \lvert0\rangle ⊗ \lvert1\rangle, \lvert1\rangle ⊗ \lvert0\rangle, \lvert1\rangle ⊗ \lvert1\rangle$$
If you apply the tensor product of it, you will end up with a $4$ basis system for $2$ qubits ($2^2$).
If you are looking for a introduction material I think that the Lecture Notes from Ronald de Wolf is a good start. It is possible to get directly from his website and it is for free. He gave a better explanation about this on section 1.3.
I hope that I have helped you.
-
$\begingroup$ The computer power grows more quickly with the addition of qubits vs bits, but it still seems to grow linearly vs what so many folks claim with an exponential increase. This is where I struggle to make sense of the claims. $\endgroup$ Commented Feb 20, 2020 at 4:26
$\begingroup$
$\endgroup$
By saying that a quantum computer using $n$ qubits does (up to) $2^n$ computations in parallel, one tries to explain quantum parallelism: If you represent the state of the $n$ qubits using probability amplitudes for each state in the computational basis, there are $2^n$ such probability amplitudes that a classical computer would have to update per quantum gate it is to simulate, whilst a quantum computer does this automatically (but with potentially less benefit since not all these numbers can be independently measured).