41–50 of 104 posts
Earlier quoted context omitted.
Surface area is squared, volume is cubed, a larger object has to get hotter to expell the same amount of heat. Per unit of volume, your body produces more heat than the sun, exactly because it is an exponential function.
Huh? What are you saying is an exponential function? x^3 is not an exponential function, in the sense relevant here.
> Researchers like Jaime Sevilla and Jess Riedel support this timeline, publishing a report in late 2020 that claimed a 90% confidence of RSA-2048 being factored before 2060. I am skeptical. 36 years is a long time, but in the past 10 years there hasn't been much progress: year 2001: factorization of 15 (IBM) year 2012: factorization of 21 (University of Bristol) year 2019: factorization of 35 attempt, failed (IBM) h…
Co-author of the paper here. The “largest integer factored” metric is terrible for several reasons, which is well recognized by researchers and is why people rarely publish those sorts of claims any more. Without net-positive error correction, it’s basically a function of how low your error rate is and how many bits that allows you to compute on with low chance of error, but as soon as the error rate crosses the faul…
Additionally, I was under the impression that not all QCs being built are able of executing Shor’s algorithm which added additional challenges that aren’t solved.
My final impression is that having the QC algorithm run faster than a classical computer doing the same operation has also not necessarily gotten better so we don’t even know if we are actually closer to Quantum supremacy in terms of actually useful more general computation instead of the limited supremacy that Google achieved in 2019 on specific problems, similar to the (still ongoing?) controversy whether DWave built a QC or a quantum annealer capable of accelerating simulations of very specific physical properties.
Is this impression outdated and/or misinformed? Would love to update my priors.
Earlier quoted context omitted.
IIRC none of those uses of shor's algorithm were real (well maybe the 2019 one was, but that failed). There's a threshold you need to reach for quantum error correction to work and we are approaching it pretty steadily on a log scale.
Quantum error correction produces logical qubits that have smaller nonzero error rate. Thus it needs to be applied repeatedly to achieve a necessary error rate to produce meaningful results. For Shor algorithm the error rate needs to decrease exponentially with the number of qubits. Thus even though IBM has a hundred qubits QCs they still only have managed to use five qubits to factorize a number 21.
I have never seen a result like that. Do you have a citation?
Earlier quoted context omitted.
>It must get exponentially harder per qbit to eliminate thermal noise by cooling down closer to absolute zero Why? Cooling a large object is not exponentially harder than cooling a small object.
Not the size, but the temperature. If you have to cool to a microkelvin for a certain number of qbits to retain coherence, how low do you need to go to add one more qbit, and how much energy will that require? My thermodynamic instinct says that the cooling effort required rises with the resolving power — which is exponential with the number of qbits. But it's just instinct, not grounded very well in science or engin…
Is this really an appropriate use of arxiv? I thought it was for physics preprints. This might be a neat work, but it appears to be a 143 page blog post in a PDF (unless I missed the references section?)
This is in the arXiv section called “physics and society” which is specifically intended for high-quality popular physics book, among other things.
Earlier quoted context omitted.
Co-author of the paper here. The “largest integer factored” metric is terrible for several reasons, which is well recognized by researchers and is why people rarely publish those sorts of claims any more. Without net-positive error correction, it’s basically a function of how low your error rate is and how many bits that allows you to compute on with low chance of error, but as soon as the error rate crosses the faul…
I thought the error rate has stayed pretty exponential in terms of the number of physical qubits needed to express a logical qubit and it’s not actually known if we’re any closer on that metric vs other more easily achieved metrics. Additionally, I was under the impression that not all QCs being built are able of executing Shor’s algorithm which added additional challenges that aren’t solved. My final impression is t…
> For example, would quantum computers work by trying all possible answers in parallel? Sorry, no, that's too good to be true: Quantum computers work by choreographing a pattern of interference, where the contributions to the amplitude of each wrong answer cancel each other out, while the contributions to the right answer's amplitude reinforce each other. Only for special problems, as it turns out, do we know how to…
Neither NP or NP∩coNP, are contained in BQP, for those that want a complexity theory version of the above. BQP: Bounded-Error Quantum Polynomial-Time, bounded by a max error of 1:3 BQP is the complexity class thought to contain problems with practical solutions for quantum computers. IIRC the main limit being the transition amplitudes are subject to the Church–Turing thesis and must be computable functions. Hopefully…
I'm more familiar with cryptography so the most famous problem in BQP for me is discrete logarithm. Once you have this primitive, the following things are very clear:
1. How Shor's algorithm for factorization works: it consists of a classical algorithm that reduces factorization to calculation of group order of an element (which is a special case of discrete logarithm), then uses a quantum computer to solve the group order problem. This breaks RSA.
2. Breaking elliptic cryptography: Modern elliptic cryptography constructs an elliptic curve (in the form of y^2=x^3+Ax+B) and defines multiplication on top of the points on the curve. It turns out that multiplication is very easy but discrete logarithm is hard and that hardness is used to prove that Diffie-Hellman key exchange is hard to break, but what if it's not? Moreover, elliptic curves usually only have 256~512 bits since it's sufficient to guarantee security in the classical case, compared to RSA with 2048~4096 bits. While it's harder to break elliptic curves using classical methods, it turns out to be even easier for quantum computers.
What quantum computers is NOT is a parallel computer with 2^n threads running in parallel that would collapse to the thread that gives the correct results. This would imply BQP=NP which is not known to be true and however many qubits we build it won't be any more likely to become true.
Earlier quoted context omitted.
Co-author of the paper here. The “largest integer factored” metric is terrible for several reasons, which is well recognized by researchers and is why people rarely publish those sorts of claims any more. Without net-positive error correction, it’s basically a function of how low your error rate is and how many bits that allows you to compute on with low chance of error, but as soon as the error rate crosses the faul…
Which metrics would be more meaningful?
Earlier quoted context omitted.
I thought the error rate has stayed pretty exponential in terms of the number of physical qubits needed to express a logical qubit and it’s not actually known if we’re any closer on that metric vs other more easily achieved metrics. Additionally, I was under the impression that not all QCs being built are able of executing Shor’s algorithm which added additional challenges that aren’t solved. My final impression is t…
A QC that can't run Shor's algorithm is not a QC, as much as D-Wave screams and stamps their feet that it's not fair.
In practice, the first useful QCs will probably be Q-Turing complete.