Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

New silicon structure opens the gate to quantum computers

princeton.edu

Post reply on HN
Print view View original

41–50 of 59 posts

Re: New silicon structure opens the gate to quantum computers

#41

Post by xxs »

jcoffland wrote: post #36
tim-- wrote: post #10

My biggest pet peeve about quantum computing is that no one can answer me the question of "what can quantum computing do for me?". The answer I hear is that it helps solve the traveling salesman in record time, and that's all great and everything, but how will quantum computing be able to do things such as decrease the time it takes to train a RNN, or look up data in a database?

The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer. https://cstheory.stackexchange.com/questions/31084/travellin...

Indeed, I have never heard how (any) NP-complete stuff would be solved by quantum computers. It was very surprising to see it as top comment.

Re: New silicon structure opens the gate to quantum computers

#42

Post by crobin »

tim-- wrote: post #10

My biggest pet peeve about quantum computing is that no one can answer me the question of "what can quantum computing do for me?". The answer I hear is that it helps solve the traveling salesman in record time, and that's all great and everything, but how will quantum computing be able to do things such as decrease the time it takes to train a RNN, or look up data in a database?

I would expect, as the technology matures and the transistors needed become smaller, to see Quantum computers instead become quantum chips that you would install as a PCI-Express card just like a GPU and would assist a normal CPU into solving some of the problems that quantum computing is better at.

Re: New silicon structure opens the gate to quantum computers

#43

Post by Beltiras »

jcoffland wrote: post #35
bsder wrote: post #16

Earlier quoted context omitted.

> Shor’s algorithm of integer factorization would solve (and cause) a whole host of problems for us. I thought it was still an open question as to whether a quantum computer would actually be able to solve this class of problems or not. In addition, quantum computers have a great deal of noise--so quantum error correction seems to be a thing.

Shor’s algorithm can factorize integers on a quantum computer asymptoticly faster than on a classical computer but the algorithm requires at least a 128 qubit quantum computer to factor a 128 bit number and thereby break something like 128 bit RSA encryption. No one yet has, or is publicly admitting to having, a reliable 128 qubit device. In some cases, error correction can be achieved simply by running the algorithm…

Error correction is immaterial for the factoring case. You multiply the factors and if you do not get the original number you know you have to run it again.

Re: New silicon structure opens the gate to quantum computers

#44

Post by akavel »

gaze wrote: post #27
tim-- wrote: post #10

My biggest pet peeve about quantum computing is that no one can answer me the question of "what can quantum computing do for me?". The answer I hear is that it helps solve the traveling salesman in record time, and that's all great and everything, but how will quantum computing be able to do things such as decrease the time it takes to train a RNN, or look up data in a database?

We don't know. If someone manages to find an algorithm to do such things, it'll be helpful for that. It's as if we're rediscovering the computer itself from the beginning and we're still not sure what it's good for, but the things we've managed to find algorithms for it appears to be really really good at. Basically, don't worry too much about it, unless you wish to hunt for such algorithms yourself. The one thing it…

Also, apart from inventing/discovering new algorithms, there's another part in inventing how to use them to help in particular "real-world" (or "non-quantum programmer world") problems. So, maybe one of the known algorithms could actually somehow help with "training a RNN", but probably nobody invented a way to rephrase ("refactor") the "training a RNN" problem in a way which could get boosted by one of the known quantum algos (the set of which can be looked at as "the quantum API") yet.

Now that I think of it, the few most well known algorithms (like the Shor's one) are probably so because "real world" use cases were found for them, which are understandable to non-quantum engineers (i.e. "factorization of primes"), as opposed to "transforming a hamiltonian foobzdringle into a hilbertian mesoism in laplacian meta-subordinates" :P

Re: New silicon structure opens the gate to quantum computers

#45

Post by visarga »

jcoffland wrote: post #36
tim-- wrote: post #10

My biggest pet peeve about quantum computing is that no one can answer me the question of "what can quantum computing do for me?". The answer I hear is that it helps solve the traveling salesman in record time, and that's all great and everything, but how will quantum computing be able to do things such as decrease the time it takes to train a RNN, or look up data in a database?

The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer. https://cstheory.stackexchange.com/questions/31084/travellin...

> The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer.

That's only a problem if you need the exact solution. If you're OK with 99.9% quality, approximate solutions are much cheaper. So the question is, is it necessary to invest into that 1%?

Re: New silicon structure opens the gate to quantum computers

#46

Post by visarga »

lisper wrote: post #31
himom wrote: post #17

Earlier quoted context omitted.

There is no added Turing power to QC over CC. Turing complete is Turing complete. Think of QC as a coprocessor for certain classes of algorithms like prime factorization.

With exponential speedup. That's the big deal.

We don't know how to extract these benefits yet for real problems.

Re: New silicon structure opens the gate to quantum computers

#47

Post by CJefferson »

visarga wrote: post #45
jcoffland wrote: post #36

Earlier quoted context omitted.

The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer. https://cstheory.stackexchange.com/questions/31084/travellin...

> The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer. That's only a problem if you need the exact solution. If you're OK with 99.9% quality, approximate solutions are much cheaper. So the question is, is it necessary to invest into that 1%?

It's unclear a quantum computer can find you an approximate solution any faster either.

Re: New silicon structure opens the gate to quantum computers

#48

Post by monob »

visarga wrote: post #45
jcoffland wrote: post #36

Earlier quoted context omitted.

The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer. https://cstheory.stackexchange.com/questions/31084/travellin...

> The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer. That's only a problem if you need the exact solution. If you're OK with 99.9% quality, approximate solutions are much cheaper. So the question is, is it necessary to invest into that 1%?

Do you have a paper on approximating NP complete problems and the bounds on the error in the solution?

Re: New silicon structure opens the gate to quantum computers

#49

Post by adrianN »

tim-- wrote: post #10

My biggest pet peeve about quantum computing is that no one can answer me the question of "what can quantum computing do for me?". The answer I hear is that it helps solve the traveling salesman in record time, and that's all great and everything, but how will quantum computing be able to do things such as decrease the time it takes to train a RNN, or look up data in a database?

To me the most exciting prospect is exponentially faster simulation of quantum systems. Computational chemistry really sucks because either you rely on heuristics or you can't simulate systems with more that a handful of atoms. If we had big quantum computers we might make real inroads into understanding protein folding and could figure out how to make artificial proteins to use for all kinds of applications. Proteins are Nature's nano-robots. Full Drexler nanotechnology awaits.

Re: New silicon structure opens the gate to quantum computers

#50

Post by [deleted] »

xxs wrote: post #41
jcoffland wrote: post #36

Earlier quoted context omitted.

The traveling salesman problem is NP-complete and therefore not known to be solvable in less time on a quantum computer. https://cstheory.stackexchange.com/questions/31084/travellin...

Indeed, I have never heard how (any) NP-complete stuff would be solved by quantum computers. It was very surprising to see it as top comment.

[deleted]
Post reply on HN