Hacker News Reader

Comment by Asdfbla | Hacker News Reader

How long does a computation step in a quantum computer (which I guess is technically a measurement) actually take? I'm (at a superficial level) aware of Grover's and Shor's algorithms, but only in the sense that they provide asymptotic speedups in the number of steps required for the computation. In classical computers it's easy to envision some model where a step is just some constant number of cycles or whatever, but how long do the measurements take in quantum computers?

I guess it depends on the specific experimental setup of your quantum computer somehow, but I'm just curious about the real-world speeds. A hypothetical computer that does few steps but takes a minute for each measurement wouldn't be so useful.

View on HN

For superconducting qubits, without error correction, each operation takes tens of nanoseconds.

With error correction... it depends how many spare qubits you have. All the non-trivial operations are done by "magic state distillation", where you produce special states in one part of the computer then consume them to perform the operation elsewhere. The more qubits you have, the more space you can allocate to magic state factories.

For example, a 32-bit addition can be done with 124 |T> states [1]. If you have N qubits allocated to factories then you can expect to get about 100N magic states per second. So if you have a tiny computer with 20 qubits dedicated to a factory, then a single addition will take over half a second. But if you can spare 2000 qubits for factories (about the same amount of qubits you'd need to store the problem in the first place) then you'd be producing T-states at 200KHz and 32-bit-adding at 1600Hz.

Shor's algorithm is, effectively, a single modular exponentiation. Performing an N-bit modular exponentiation requires something like 4N^3 |T> states. So 1024^3*4/200KHz = 6 hours to a factor a 1024 bit key, assuming 2000 qubits on factories and that the other rough numbers are close.

1: https://arxiv.org/abs/1709.06648

It depends on the implementation. Ion traps are slower than superconducting qubits, for example, although they are speeding up. This paper, from 2014, gives some parameters:

  "Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing"  
  Campbell et al.  
  Nature, 2014

https://arxiv.org/abs/1402.4848

From page 9:

Initialization ~50ns

Measurement ~200ns

One-qubit gates ~20ns

Two-qubit gates ~40ns

Single measurement collapses to some fixed state. You need to reset the whole thing and do measurement again. Repeat it many times and you'll start seeing distribution that you're interested in. Your solution/algo will amplify correct answers.

Single measurement is like revealing single pixel of a picture. If you do it enough times, you know what's on the picture.

Yeah, so the question is about the order of magnitude it takes for each such simple measurement; how much time does it take to reset the whole thing and do measurement again - how many times per second/hour/whatever can we hope do do that.

And how many times do you need to do it to get the precision you want?

The importance of quantum computers is not the absolute clock speed, but rather the ability to reduce previously exponential problems into sub exponential complexity.

For example take the classic attacks on DLP -- instead of essentially manually factoring the keys we can create a program (Shor's algorithm, etc) that essentially treats the problem of factoring as the task of determining the base frequencies of the key when treating the public component as a wave (at least as I understand it).

On an ideal quantum computer that task should be polynomial complexity, although there's still some (hopefully small) probability of error, but basically you just repeat many times and use a classical computer to verify the solution.

Reply on news.ycombinator.com