Does anybody have any other comparisons between a universal quantum computer and a classical computer that might shed some light into how their performance compares?
Below is what I've been able to come up with, so far.
I am an electrical engineer and have been learning about quantum computing for the last year, and I can hardly believe what I read and hear. It is becoming clearer to me, but it's a very difficult subject.
Why is there so much fuss about quantum computing? I will attempt here to show that a 19 qubit quantum computer could match the performance of a 200 petaflops IBM supercomputer, and also how its performance improves with more qubits.
This discussion assumes that all of these qubits are what are termed 'logical qubits'. That is, they are fully error-corrected and have infinite 'coherence' times. These types of qubits are a LONG way off. Contemporary 2019 qubits are short-lived.
First, the state of a quantum computer is defined by a vector of length 2^n complex values where n is the number of qubits in that quantum computer. For example:
1 qubit -> 2 values in the state vector
2 qubits -> 4 values in the state vector
3 qubits -> 8 values in the state vector
16 qubits -> 65,536 values in the state vector
100 qubits -> 1,267,650,600,228,229,401,496,703,205,376 values in the state vector
and so on.
The square of any one of the values in the state vector list indicates the probability that this particular list number (index) will be observed at the output of the quantum computer when the MEASURE logic gate (see below) is finally applied.
To program the quantum computer, a person will apply what are called 'quantum logic gates' or just 'gates' to the system in order to achieve the processing that they desire. Some of the names of the 'gates' are Hadamard, CNOT, Pauli-X, and MEASURE (the last one applied).
When a programmer starts to manipulate the quantum computer, the state of the qubits is initialized and the first value in the state vector list is set equal to 'one' and all of the other values are set equal to 'zero'. If the MEASURE gate were applied now then the output would always read 0b0...00000 since the probability of observing that first list number is 100%.
The goal of the programmer is usually to apply the necessary quantum logic 'gates' in such a way that the 100% list value moves from list entry number 0b0...00000 to some other list entry number, and that number is what the scientists have been waiting for.
Each logic gate takes less than one microsecond to complete, and what each gate does is to modify all of the 2^n current state vector values in order to create (evolve to) the next state vector list. This is equivalent to a 2^n by 2^n matrix multiplied with the 2^n current state vector. This is 2^n * 2^n = 2^2n multiply/accumulate (MAC) operations in one microsecond.
A contemporary IBM supercomputer allegedly has 200 petaflops of performance. If we let one FLOP (floating-point operation) equal one MAC (multiply/accumulate) operation then the IBM classical computer can do 200*10^15 MACS/sec * 10^-6 sec = 200*10^9 MACs in one quantum computer gate time.
So, equating the quantum computer to the IBM supercomputer's performance (for one quantum gate time): 2^2n = 200*10^9 or n = 18.7 qubits (19 qubits) in order for a quantum computer to match the MAC performance of an IBM 200 petaflop supercomputer.
This is really amazing, and assuming that this is generally correct then each additional qubit means a 4x increase in MAC performance. Scientists are talking about applications requiring 500 qubits. It's going to be interesting.