News for hackers. Stuff that matters.
Re:Quantum Factorization of 143 (2011) by curuinor on Wednesday September 16, 2020 @07:00PM (#24499048)
Quantum adiabatic means no proved exponential speedup. I mean, we've factored stuff with 143 _digits_ with general number field sieve, the only interest is in the exponential speedup
Re:Quantum Factorization of 143 (2011) by est31 on Wednesday September 16, 2020 @07:11PM (#24499147)
Is this true? After reading your comment I looked up what adiabatic quantum computation is and found this [0]:

> We give an example of an adiabatic quantum algorithm for searching that matches the optimal quadratic speedup obtained by Grover’s search algorithm. This example demonstrates that the ‘quantum local search’, which is implicit in the adiabatic evolution, is truly non-classical in nature from a computational viewpoint.

[0]: https://people.eecs.berkeley.edu/~vazirani/pubs/adiabatic.pd...

Re:Quantum Factorization of 143 (2011) by anderskaseorg on Wednesday September 16, 2020 @07:34PM (#24499348)
Compared to the extremely slow trial division algorithm (~2^(n/2) for an n bit number), it’s true that Grover’s algorithm (and perhaps this adiabatic algorithm) gives a significant speedup (~2^(n/4))—but that’s useless, because the best known classical factoring algorithms are already much faster than that (~5.5^∛n), and Shor’s quantum algorithm would be much, much faster still (~n²).

(Note that, strictly speaking, the best classical algorithms are already sub-exponential, i.e., faster than C^n for all C, so there’s no such thing as an “exponential speedup”.)

Quotes from Scott Aaronson about the adiabatic factorization of 143: “It doesn’t ‘know’ about the special mathematical properties of factoring that make that an easy problem for quantum computers. In contrast to Shor’s algorithm, we have no reason to think it would be able to factor 10,000 digit numbers in less than astronomical amounts of time.… I didn’t see any evidence that quantum behaviour played a role in finding the factors of 143.”

https://www.newscientist.com/article/dn21699-controversial-q...

Re:Quantum Factorization of 143 (2011) by bollu on Wednesday September 16, 2020 @08:02PM (#24499561)
Grover's search offers quadratic (polynomial) speedup, not exponential. As OP states, adiabatic does not provide for the theoretical possible exponential speedup, assuming the hypothetical relations of complexity classes P != (NP = BQP) holds. That is: P and NP are different, so there are "hard exponential problems" like 3-SAT. Also, NP = BQP, so quantum computers can solve these hard problems.
Re:Quantum Factorization of 143 (2011) by anderskaseorg on Wednesday September 16, 2020 @08:14PM (#24499670)
We have no evidence that factoring is NP-hard, and some evidence that it probably isn’t: the best known classical algorithms for factoring are much faster than those for NP-complete problems. We have no idea whether NP = BQP, or indeed whether either is contained in the other.
Re:Quantum Factorization of 143 (2011) by bollu on Wednesday September 16, 2020 @08:16PM (#24499689)
Yes, which is why I phrased all of this as "hypothetical relations ..."
Re:Quantum Factorization of 143 (2011) by kmckiern on Wednesday September 16, 2020 @09:13PM (#24500091)
Re:Quantum Factorization of 143 (2011) by anderskaseorg on Wednesday September 16, 2020 @07:18PM (#24499213)
This is from 2011.