4 ms·

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 t

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

est31 6y ago
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.pdf https://people.eecs.berkeley.edu/~vazirani/pubs/adiabatic.pd...
- anderskaseorg 6y ago
  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-quantum-computer-beats-factoring-record/ https://www.newscientist.com/article/dn21699-controversial-q...
- bollu 6y ago
  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.
  - anderskaseorg 6y ago
    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.
    - bollu 6y ago
      Yes, which is why I phrased all of this as "hypothetical relations ..."
kmckiern 6y ago
false. https://arxiv.org/abs/quant-ph/0405098 https://arxiv.org/abs/quant-ph/0405098

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

est31 6y ago

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.pdf https://people.eecs.berkeley.edu/~vazirani/pubs/adiabatic.pd...

anderskaseorg 6y ago
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-quantum-computer-beats-factoring-record/ https://www.newscientist.com/article/dn21699-controversial-q...
bollu 6y ago
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.
- anderskaseorg 6y ago
  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.
  - bollu 6y ago
    Yes, which is why I phrased all of this as "hypothetical relations ..."

kmckiern 6y ago

false. https://arxiv.org/abs/quant-ph/0405098 https://arxiv.org/abs/quant-ph/0405098