3 ms·

The algorithms that are touted as offering a pathway to quantum Supremacy, by Shor[1] and Grover[2] both rely on the Quantum Fourier Transform[3], which include

The algorithms that are touted as offering a pathway to quantum Supremacy, by Shor[1] and Grover[2] both rely on the Quantum Fourier Transform[3], which includes a large number of iterations through a Controlled Phase Shift Gate[4]. Those phase angles are crucial to the success of the QFT. Any error in the phase can not be corrected with current methods of Quantum Error Correction[5], which focus strictly on making sure that Qubits are in a "pure" state, essentially ignoring phase. I thus include that Quantum Gate Computing is all hype. The approach Dwave took, of quantum annealing[6], seems to offer some hope of real world performance surpassing that of conventional computing. However, there may be some algorithm out there that can do that annealing faster on conventional hardware. Also, there may be a way of using analog electronics to simulate annealing much faster than can be done currently in a program. [1] https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm [2] https://en.wikipedia.org/wiki/Grover%27s_algorithm https://en.wikipedia.org/wiki/Grover%27s_algorithm [3] https://en.wikipedia.org/wiki/Quantum_Fourier_transform https://en.wikipedia.org/wiki/Quantum_Fourier_transform [4] https://en.wikipedia.org/wiki/Quantum_logic_gate#Phase_shift_gates https://en.wikipedia.org/wiki/Quantum_logic_gate#Phase_shift... [5] https://en.wikipedia.org/wiki/Quantum_error_correction https://en.wikipedia.org/wiki/Quantum_error_correction [6] https://en.wikipedia.org/wiki/Quantum_annealing https://en.wikipedia.org/wiki/Quantum_annealing

orlp 4y ago
This paper [1] claims that with their implementation they can get an AQFT (approximate QFT) with sufficient precision to factor RSA-2048 with < 0.01% error probability using 2083 qubits, 364,510 CNOT gates and 196,234 T gates, both of which can be error corrected. [1] https://www.nature.com/articles/s41534-020-0257-5 https://www.nature.com/articles/s41534-020-0257-5 Just because textbook QFT requires ever increasingly precise gates does not mean that this can't be worked around. If you want to do useful quantum computation you have to embrace error bounds, precision loss and probabilistic computing, which makes it quite difficult. But not impossible.
- mikewarot 4y ago
  I looked at their source code[1], which is indeed a listing of quantum gates, but no actual code that I could run. I'd be interested to see this run in simulation even on a very small N with realistic levels of errors. [1] https://github.com/y-nam/QFT https://github.com/y-nam/QFT
Strilanc 4y ago
In a decent sized quantum Fourier transform, almost all of the phase gates are rotating by extremely tiny angles. For example, in a thousand qubit Fourier transform, 99% of the phase gates are rotating by an angle that is less than 0.000000000000000000000000001 degrees. That amount of rotation is irrelevant. You can skip 99.9% of the phase gates and the output will be de-facto indistinguishable from the ideal output. There's really a surprising amount of flexibility in the phasing.
krastanov 4y ago
Your second paragraph does not make much sense to me. Pretty much any quantum error correcting code being pursued today deals both with phase-flips and bit-flips. The comment about "pure" state also does not make much sense to me: a qubit afflicted by phase noise would not be in a pure state. I think you might be using the word "pure" in a way that is not the typical way it is used in the field. Maybe you are trying to say that the more toy-like codes that have been demonstrated today, like the repetition code, do not protect against phase flips. That is true, these "easy" codes that are small enough for demonstrations on today's immature hardware indeed do not protect against all types of errors. But codes like the toric code or qLDPC codes do protect both against phases errors and bit-flip errors. They are just too expensive to implement on today's immature hardware. Lastly, no, Dwave's annealing approach is not particularly promising compared to others. Annealing does not provide real-world performance boost compared to classical computers unless you have error-corrected qubits.
- mikewarot 4y ago
  I'm not talking about phase flips, but actual accumulated phase rotation due to noise, error, cross-talk, etc. Quantum error correction is geared towards keeping a Qubit in alignment with some axis through the Bloch sphere, at the two poles where it intersects the Bloch sphere. In order for the QFT to work, you have to be able to rotate around at least one axis, not near its poles.
  - krastanov 4y ago
    I still do not understand. Quantum error correction does not require the qubit to be in a particular orientation on the Bloch sphere: any point on the Bloch sphere is equally protected. Are you saying that certain gates are simply difficult to perform precisely, e.g. that they will always have some systematic over-rotation? That also seems to be fixable with what is called randomized compiling.
    - mikewarot 4y ago
      Any point on the Bloch sphere can be protected... any discrete point, or set of points... but QFT and the rotations it depends upon are analog operations, not discrete.

orlp 4y ago

This paper [1] claims that with their implementation they can get an AQFT (approximate QFT) with sufficient precision to factor RSA-2048 with < 0.01% error probability using 2083 qubits, 364,510 CNOT gates and 196,234 T gates, both of which can be error corrected. [1] https://www.nature.com/articles/s41534-020-0257-5 https://www.nature.com/articles/s41534-020-0257-5 Just because textbook QFT requires ever increasingly precise gates does not mean that this can't be worked around. If you want to do useful quantum computation you have to embrace error bounds, precision loss and probabilistic computing, which makes it quite difficult. But not impossible.

mikewarot 4y ago
I looked at their source code[1], which is indeed a listing of quantum gates, but no actual code that I could run. I'd be interested to see this run in simulation even on a very small N with realistic levels of errors. [1] https://github.com/y-nam/QFT https://github.com/y-nam/QFT

Strilanc 4y ago

In a decent sized quantum Fourier transform, almost all of the phase gates are rotating by extremely tiny angles. For example, in a thousand qubit Fourier transform, 99% of the phase gates are rotating by an angle that is less than 0.000000000000000000000000001 degrees. That amount of rotation is irrelevant. You can skip 99.9% of the phase gates and the output will be de-facto indistinguishable from the ideal output. There's really a surprising amount of flexibility in the phasing.

krastanov 4y ago

Your second paragraph does not make much sense to me. Pretty much any quantum error correcting code being pursued today deals both with phase-flips and bit-flips. The comment about "pure" state also does not make much sense to me: a qubit afflicted by phase noise would not be in a pure state. I think you might be using the word "pure" in a way that is not the typical way it is used in the field. Maybe you are trying to say that the more toy-like codes that have been demonstrated today, like the repetition code, do not protect against phase flips. That is true, these "easy" codes that are small enough for demonstrations on today's immature hardware indeed do not protect against all types of errors. But codes like the toric code or qLDPC codes do protect both against phases errors and bit-flip errors. They are just too expensive to implement on today's immature hardware. Lastly, no, Dwave's annealing approach is not particularly promising compared to others. Annealing does not provide real-world performance boost compared to classical computers unless you have error-corrected qubits.

mikewarot 4y ago
I'm not talking about phase flips, but actual accumulated phase rotation due to noise, error, cross-talk, etc. Quantum error correction is geared towards keeping a Qubit in alignment with some axis through the Bloch sphere, at the two poles where it intersects the Bloch sphere. In order for the QFT to work, you have to be able to rotate around at least one axis, not near its poles.
- krastanov 4y ago
  I still do not understand. Quantum error correction does not require the qubit to be in a particular orientation on the Bloch sphere: any point on the Bloch sphere is equally protected. Are you saying that certain gates are simply difficult to perform precisely, e.g. that they will always have some systematic over-rotation? That also seems to be fixable with what is called randomized compiling.
  - mikewarot 4y ago
    Any point on the Bloch sphere can be protected... any discrete point, or set of points... but QFT and the rotations it depends upon are analog operations, not discrete.