4 ms·

> 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 choreog

> 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 choreograph such an interference pattern to deliver a huge speedup over the best known classical algorithms. This, in turn, is why we don't expect quantum computers ever to replace classical computers, but “merely” to complement them, accelerating specific tasks like quantum simulation and codebreaking. I'm not sure about the field of physics but in deep learning there are hundreds of papers published every day while no more than a percent of them tries to make the paper less mythical and instead they keep inventing buzzwords and claiming positive results to make them even more mythical

_heimdall 2y ago
That phenomenon isn't specific to physics or deep learning. Academic papers are more and more of a joke these days. Sure there's plenty of good work being done too, but its be buried in a pile of poorly done research and deceiving statistics that are written only to chase funding and/or recognition for the author (promotions, graduation, jobs, etc).
nyrikki 2y ago
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 useful buzzwords for those who want to dig deeper.
- renonce 2y ago
  Yeah these buzzwords are very useful pointers to wikipedia pages with details on what problems are in which complexity class and what are not. 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.

_heimdall 2y ago

That phenomenon isn't specific to physics or deep learning. Academic papers are more and more of a joke these days. Sure there's plenty of good work being done too, but its be buried in a pile of poorly done research and deceiving statistics that are written only to chase funding and/or recognition for the author (promotions, graduation, jobs, etc).

nyrikki 2y ago

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 useful buzzwords for those who want to dig deeper.

renonce 2y ago
Yeah these buzzwords are very useful pointers to wikipedia pages with details on what problems are in which complexity class and what are not. 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.