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

21–30 of 30 posts

Re: The First Universal Quantum Processor

#21

Post by jerf »

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…

Disclaimer: I'm not quantum-anything researcher. But: Based on the description of how "quantum encryption" works, I prefer to call it "quantum intrusion detection". It allows you to verify that the channel is free of eavesdroppers and get a stream of random bits that are guaranteed to only be agreed upon by the two ends of the connection, which can then be used for any other purpose that a stream of random bits only known by two parties can be used for. Using it for a one-time pad is the easiest thing from a theoretical point of view, but you can use it to feed a conventional encryption algorithm, too.

The real key isn't the "random", which is easily obtained from a wide variety of other sources, including fully unpredictable ones like decay sources, nor is it the "encryption" which is merely one application (though easily the "killer app") of the system. The real key is the part where you can detect any intrusion into the connection.

(Obviously, you, enki, know this, well, unless I'm wrong. I'm just elaborating.)

Re: The First Universal Quantum Processor

#22

Post by est »

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?

sleep(3) will be exact natural time three seconds, and you can't hack the system clock like SpeedGear to speed it up or slow it down on a quantum computer.

And this leads to some encryption applications.

Re: The First Universal Quantum Processor

#23

Post by sp332 »

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…

Actually, because of the inherent uncertainty, most computations are exponentially slower on a quantum computer. There are a few algorithms that manage to take advantage of entanglement and superposition to be faster, but quantum computers are not inherently faster than classical computers.

Re: The First Universal Quantum Processor

#25

Post by korch »

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.

You can use polynomial time factoring to prove P = NP. Which means you have simultaneously solved a ton of outstanding optimization problems in science and engineering, and would allow for the creation of AI, clean renewable energy and practical space travel. Obviously those innovations would lead to the biggest change in the history of human civilization, and probably would cause lasting world peace. All from something as "useless" as factoring integers. True story.

Re: The First Universal Quantum Processor

#26

Post by fauigerzigerk »

rdtsc wrote: post #12
lionheart wrote: post #5

Earlier quoted context omitted.

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…

What about the data that is searched? Where would it be stored for a quantum computer to access it without losing all the speedup on IO?

Re: The First Universal Quantum Processor

#27

Post by enki »

jerf wrote: post #21
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…

Disclaimer: I'm not quantum-anything researcher. But: Based on the description of how "quantum encryption" works, I prefer to call it "quantum intrusion detection". It allows you to verify that the channel is free of eavesdroppers and get a stream of random bits that are guaranteed to only be agreed upon by the two ends of the connection, which can then be used for any other purpose that a stream of random bits only…

hey, nice idea - but that's not how it works.

there's no intrusion detection - an attacker increases the error rate, and by the error rate we can calculate the maximum probabilistic information an attacker plausibly might have. i say can, because that number is actually pretty uninteresting, since it isn't intrusion detection - we just now there's something causing the error rate to go up - doesn't have to be an attacker. a higher error rate in practice just means we gotta throw more bits away both during error correction and during privacy amplification - which is kinda like packetloss on a classical channel.

at some point the error rate is too high for error correction with a positive yield (= more key lost in communication, than gained through said communication) - thus the scheme stops working.

my personal favorite name is 'quantum key growing', because that's essentially what happens - you turn an initial shared secret (= random key) into a longer random key. (and while you're continually doing this, you're using up part of the previous key to secure communication as you go along)

Re: The First Universal Quantum Processor

#29

Post by jerf »

enki wrote: post #27
jerf wrote: post #21

Earlier quoted context omitted.

Disclaimer: I'm not quantum-anything researcher. But: Based on the description of how "quantum encryption" works, I prefer to call it "quantum intrusion detection". It allows you to verify that the channel is free of eavesdroppers and get a stream of random bits that are guaranteed to only be agreed upon by the two ends of the connection, which can then be used for any other purpose that a stream of random bits only…

hey, nice idea - but that's not how it works. there's no intrusion detection - an attacker increases the error rate, and by the error rate we can calculate the maximum probabilistic information an attacker plausibly might have. i say can, because that number is actually pretty uninteresting, since it isn't intrusion detection - we just now there's something causing the error rate to go up - doesn't have to be an atta…

Is there some interesting characteristic of the channel that you're looking for, other than intruders, though? Merely detecting the error rate on a channel is uninteresting; conventional algorithms have nailed that problem to the wall. I'm not worried about exactly how it is done, I'm thinking about what it's good for; take away the ability to detect intruders, even if that's not the only thing it may be doing, and what's left?

Re: The First Universal Quantum Processor

#30

Post by rdtsc »

fauigerzigerk wrote: post #26
rdtsc wrote: post #12

Earlier quoted context omitted.

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…

What about the data that is searched? Where would it be stored for a quantum computer to access it without losing all the speedup on IO?

Idealy only an index would be searched. For example when a sorting algorithm is presented, typically we assume that items are just integers.

So if the database itself is huge, one would take a column and feed that into the quantum computer along with a matching function and a search item and the output would be the position of the item in the column.

In general it is assumed that 'items' are integers. That is general enough. But since no practical implementations exist, still we still don't know how it would work in the real world with a real database.

Here is a more in depth (and somewhat dramatic) explanation:

For N, items to be search, it would take log2(N) qubits (that's enough to represent all N states). The matching function would have to be a quantum gate/operator. In other words, matching is performed in the quantum world.

The idea behind quantum algorithms is to encode the input in a set of qubits, then make them interact in a way that creates a superposition of states. A superposition of states can be thought of as sending the input into a 'magic' quantum world, where N qubits simoultaneously represent all 2^N binary states. Then a set of quantum operators (gates) are applied to the state vector, while it is still in this magic quantum world.

All is fine and dandy (provided that we can mentain the whole quantum world in a stable/isolated state). Then the 'sad' part is that once we measure the result and bring it into the 'real' world, the whole 'magic' quantum world collapses on itself, and only one particular state out of 2^N emerges.

The trick is then to apply the quantum operators such that the probability of the quantum world collapsing to one particular 2^N state is increased. In case of Grover's algorithm that is what happens. The quantum operators increase the probability of the quantum state collapsing to the matched index. It is a probabilistic algorithm in the sense that it might have to be run a couple of times.

EDIT: removed stupid spelling errors

Post reply on HN