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

The First Universal Quantum Processor

physorg.com

Post reply on HN
Print view View original

11–20 of 30 posts

Re: The First Universal Quantum Processor

#11

Post by amichail »

rdtsc wrote: post #10
lionheart wrote: post #2

I'm curious, what kinds of application ideas exist that are possible on quantum computers that aren't on regular computers?

Theoretically none. Quantum computers are universal Turing machines. The main advantage of quantum computers is speedup. 5 years ago (when I took a couple of courses in QC) there were basically 2 quantum algorithms -- Shor's factorization and Grover's search. The former speeds up integer factorization (and discrete logarithm) and brings it to polynomial time, and the later speeds up search from O(n) to O(sqrt(n)). So…

Where does quantum cryptography fit into this?

http://en.wikipedia.org/wiki/Quantum_cryptography

Does this have anything to do with quantum computing?

Re: The First Universal Quantum Processor

#12

Post by rdtsc »

lionheart wrote: post #5
amichail wrote: post #3

Earlier quoted context omitted.

Factoring is possible in polynomial time.

See, I've heard this before. But it really doesn't mean anything to most people. The only concrete example I can think of is cracking modern encryption. Does anybody have any ideas that would be useful to everyday life? I'm 100% sure that there are a ton.

Well unless users work for NSA, are somehow aware of encryption algorithms, are concerned about protecting their data, or are interested in factoring large numbers, this would not interest them much.

Grover's search algorithm however, will speedup searching. It would be possible to search very large databases in a much shorter time : O(sqrt(n)) instead of O(n). Of course, many problems are based on searching so it is hard to enumerate all the possible end-user visible effects of this.

Re: The First Universal Quantum Processor

#13

Post by rdtsc »

amichail wrote: post #11
rdtsc wrote: post #10

Earlier quoted context omitted.

Theoretically none. Quantum computers are universal Turing machines. The main advantage of quantum computers is speedup. 5 years ago (when I took a couple of courses in QC) there were basically 2 quantum algorithms -- Shor's factorization and Grover's search. The former speeds up integer factorization (and discrete logarithm) and brings it to polynomial time, and the later speeds up search from O(n) to O(sqrt(n)). So…

Where does quantum cryptography fit into this? http://en.wikipedia.org/wiki/Quantum_cryptography Does this have anything to do with quantum computing?

You are right, thank you. I embarrassingly forgot quantum cryptography.

Re: The First Universal Quantum Processor

#14

Post by amichail »

rdtsc wrote: post #13
amichail wrote: post #11

Earlier quoted context omitted.

Where does quantum cryptography fit into this? http://en.wikipedia.org/wiki/Quantum_cryptography Does this have anything to do with quantum computing?

You are right, thank you. I embarrassingly forgot quantum cryptography.

But it seems that quantum cryptography allows you to do more than what is possible with classical computing: namely, to detect someone listening in on your communication.

What is the relationship between quantum cryptography and quantum computing?

Re: The First Universal Quantum Processor

#15

Post by enki »

rdtsc wrote: post #13
amichail wrote: post #11

Earlier quoted context omitted.

Where does quantum cryptography fit into this? http://en.wikipedia.org/wiki/Quantum_cryptography Does this have anything to do with quantum computing?

You are right, thank you. I embarrassingly forgot quantum cryptography.

you were right to leave it out - quantum cryptography and quantum computing have only the quantum in common. (i've published on quantum cryptography protocols)

Re: The First Universal Quantum Processor

#16

Post by amichail »

enki wrote: post #15
rdtsc wrote: post #13

Earlier quoted context omitted.

You are right, thank you. I embarrassingly forgot quantum cryptography.

you were right to leave it out - quantum cryptography and quantum computing have only the quantum in common. (i've published on quantum cryptography protocols)

Could you elaborate on this?

Classical encryption can be done on a classical computer.

Is it the case that (some) quantum encryption cannot be done on a quantum computer?

Re: The First Universal Quantum Processor

#17

Post by enki »

amichail wrote: post #16
enki wrote: post #15

Earlier quoted context omitted.

you were right to leave it out - quantum cryptography and quantum computing have only the quantum in common. (i've published on quantum cryptography protocols)

Could you elaborate on this? Classical encryption can be done on a classical computer. Is it the case that (some) quantum encryption cannot be done on a quantum computer?

quantum cryptography isn't "encryption" in the sense that crypto algorithms are involved. the encryption part is just XOR with a random one-use string (the key). the hard part is distributing that key.

a better name is quantum key distribution. entangled photons are used to get the random data to both parties in a way that eavesdroppers would introduce error (because of something called quantum indeterminancy).

since no computation is involved, there's not a lot relation to quantum computing. wikipedia's got the details!

Re: The First Universal Quantum Processor

#18

Post by amichail »

enki wrote: post #17
amichail wrote: post #16

Earlier quoted context omitted.

Could you elaborate on this? Classical encryption can be done on a classical computer. Is it the case that (some) quantum encryption cannot be done on a quantum computer?

quantum cryptography isn't "encryption" in the sense that crypto algorithms are involved. the encryption part is just XOR with a random one-use string (the key). the hard part is distributing that key. a better name is quantum key distribution. entangled photons are used to get the random data to both parties in a way that eavesdroppers would introduce error (because of something called quantum indeterminancy). since…

This isn't something that a Turing machine can do.

Why not make this part of a quantum computational model that goes beyond Turing-completeness?

Re: The First Universal Quantum Processor

#19

Post by dave_au »

amichail wrote: post #3
lionheart wrote: post #2

I'm curious, what kinds of application ideas exist that are possible on quantum computers that aren't on regular computers?

Factoring is possible in polynomial time.

From what I can remember, Schors algorithm gives you a polynomial speedup for factoring rather than putting it in polynomial time.

It's been a little while since I was up to speed on this though.

Re: The First Universal Quantum Processor

#20

Post by smanek »

amichail wrote: post #18
enki wrote: post #17

Earlier quoted context omitted.

quantum cryptography isn't "encryption" in the sense that crypto algorithms are involved. the encryption part is just XOR with a random one-use string (the key). the hard part is distributing that key. a better name is quantum key distribution. entangled photons are used to get the random data to both parties in a way that eavesdroppers would introduce error (because of something called quantum indeterminancy). since…

This isn't something that a Turing machine can do. Why not make this part of a quantum computational model that goes beyond Turing-completeness?

Because it isn't a computation (in the 'transform data' or 'answer question' sense).
Post reply on HN