We consider Shor's quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) rotation gates, we prove that the algorithm does not factor integers of the form $pq$ when the noise exceeds a vanishingly small level in terms of $n$ -- the number of bits of the integer to be factored, where $p$ and $q$ are from a well-defined set of primes of positive density. We further prove that with probability $1 - o(1)$ over random prime pairs $(p,q)$, Shor's factoring algorithm does not factor numbers of the form $pq$, with the same level of random noise present.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
Lemonnier only cites
pp22
A first approach to programming with quantum effects is the quantum λ-calculus [SV09]. Nevertheless, that language does not handle quantum programming as an algebraic effect, since it requires measurement into classical data to control the flow of execution.
pp23 1st para has more of the same
In the quantum λ-calculus, a qubit has to be measured before influencing the control of a program. These models are not of interest to this thesis, because the use of measurement breaks superposition, therefore it does not preserve the aforementioned quantum effect.
[SV09] Peter Selinger and Benoit Valiron. Quantum lambda calculus. Semantic techniques in…
Read the full comment
quantum computation, pages 135–172, 2009.
Keye Martin: be right back (I didn't see much there either.)
in my own heap: one might be able to use Scott continuity to replace lemma 7?
https://arxiv.org/abs/2306.10072
pp6-10 "Corrupted geometric sum"
Pay attention to how the "control gates" (as in SV09) are invoked
pp7: The crucial step in Shor’s algorithm, after the quantum Fourier transform, is to take a quantum measurement, with the property that the probability of observing a state that is close to an integral multiple of 2^n/ω is high.
pp12 has this speculation
>At its most fundamental level, it is not permitted to ask the computing machine to scan a continuously deformed symbol from ξ to ζ, while a mathematical homotopy can easily be envisioned.
There's a specific view (as I understand it) that QFT's don't scale https://arxiv.org/abs/2306.10072 but some folks seem to dismiss this for reasons I just don't grok at all.
I have forgotten the source where I stumbled on the requirement for a qubit error rate to run the Shor algorithm. I would greatly value it if someone could put a key reference here.
A recent result considers a generic error model and a subclass for particular kinds of prime numbers [1]. The important result is $epsilon > cn^{−1/3}$ where epsilon represents qubit error rate and n number of bits in the factorised number. As $n = 2^N$ where N is a number of qubits, the result:
error_rate < const/2^{N/3}
Therefore, the error rate must decrease exponentially with the number of logical qubits with which the computation is made.
[1]: https://arxiv.org/pdf/2306.10072
Yeah, for Shor's algorithm to factor an integer of order 2^k you need controlled phase gates with phases roughly order 2^{-k} (very roughly, with some caveats, but lets just say you need some small ones) these very small phase gates are susceptible to even very small errors.
This is a gross oversimplification. For the true version see here
https://arxiv.org/abs/2306.10072
I'm not sure that you are correct. I've tried to read https://arxiv.org/abs/2306.10072 in the last day and if my reading is right (I am very stretched by this stuff so I am very happy to be corrected) then no amount of error correction will rescue Shor's - only zero error phase gates. I suspect that a similar story is true for native QML, as quantum memory scales it's just going to get exponentially harder to maintain it.
The Fermi paradox is the conflict between an expectation of a high {\em ex ante} probability of intelligent life elsewhere in the universe and the apparently lifeless universe we in fact observe.
Despite their massive size, successful deep artificial neural networks can exhibit a remarkably small difference between training and test performance.
Fast compilation is important when compilation occurs at runtime, such as query compilers in modern database systems and WebAssembly virtual machines in modern browsers.
In honor of Alan Turing's hundredth birthday, I unwisely set out some thoughts about one of Turing's obsessions throughout his life, the question of physics and free will.