3 ms·

In the paper they suggest that spending ~24 hours more doing computation means you can divide the number of qubits by 24, indicating that at least in one sense

by bArray 5y ago

In the paper they suggest that spending ~24 hours more doing computation means you can divide the number of qubits by 24, indicating that at least in one sense it is linearly scalable. From my limited understanding, you process for a given amount of time, after which you can classically pull out an answer with some given probability, with some trade off with time and noise. I imagine it would be somewhat possible to have several quantum computers running in parallel which end early, each correctly deducing the answer with some given probability. If each of the N^x machines has a 1/N chance of having the correct answer, you could simply test each solution classically. And that assumes there is not some way to seed the search effort classically during the setup of the quantum circuit.

tsimionescu 5y ago
There are two aspects here. In order to implement a quantum algorithm, you need a minimum number of interacting qubits, which the article calls a qubit depth. All of these qubits must be entangled with each other in order to achieve any quantum speed-up. Below this number, your quantum algorithm simply can't be represented on the machine - it would be like trying to multiply two 128-bit numbers on a processor with 2 8-bit registers: you simply don't have enough working memory to do the calculations you need. An extra complication for QCs is that you also need error correcting calculations in addition to your base calculations. So, if you want to multiply 2 128-bit numbers, not only do you need at least 256 (q)bits of working memory, you need some additional number to correct for errors in the calculation - and with currently known error correcting methods, you need A LOT more. That's why the article is giving a minimum number of qbits for the Bitcoin calculation: 10^7 physical bits, which represent a measly ~2000 logical (perfect) qubits. This is the minimum number you would need to keep entangled for your your minimum clock period. We are currently at 10^2, and even getting to 200 is a research-level task; 10^3 is far away. Once we get to something like 10^7, we may be able to start thinking of parallelizing at the whole machine level. Even still, it's important to understand that quantum algorithms have, as far as we know for now, an exponential advantage over classical algorithms (note: this only applies to certain algorithms, NOT any algorithm). This only applies as long as you are running in the quantum regime. That is, if a particular quantum computer can resolve a problem for N components in 1 minute, and a quantum computer of double the qubit number can finish it in 30s, 2 QCs of the first type will finish it in something like 59s, since they will not benefit from the exponential quantum speedup.

by bArray 5y ago

tsimionescu 5y ago

There are two aspects here. In order to implement a quantum algorithm, you need a minimum number of interacting qubits, which the article calls a qubit depth. All of these qubits must be entangled with each other in order to achieve any quantum speed-up. Below this number, your quantum algorithm simply can't be represented on the machine - it would be like trying to multiply two 128-bit numbers on a processor with 2 8-bit registers: you simply don't have enough working memory to do the calculations you need. An extra complication for QCs is that you also need error correcting calculations in addition to your base calculations. So, if you want to multiply 2 128-bit numbers, not only do you need at least 256 (q)bits of working memory, you need some additional number to correct for errors in the calculation - and with currently known error correcting methods, you need A LOT more. That's why the article is giving a minimum number of qbits for the Bitcoin calculation: 10^7 physical bits, which represent a measly ~2000 logical (perfect) qubits. This is the minimum number you would need to keep entangled for your your minimum clock period. We are currently at 10^2, and even getting to 200 is a research-level task; 10^3 is far away. Once we get to something like 10^7, we may be able to start thinking of parallelizing at the whole machine level. Even still, it's important to understand that quantum algorithms have, as far as we know for now, an exponential advantage over classical algorithms (note: this only applies to certain algorithms, NOT any algorithm). This only applies as long as you are running in the quantum regime. That is, if a particular quantum computer can resolve a problem for N components in 1 minute, and a quantum computer of double the qubit number can finish it in 30s, 2 QCs of the first type will finish it in something like 59s, since they will not benefit from the exponential quantum speedup.