How is quantum computing supposed to work?
Instead of operating on classical bits, quantum computers can operate on qbits, which can exist in superposition. So computations can be done, if you design them correctly, that operate on these superpositions instead of on classical bits. Because of this shift in the nature of how these computations are represented, they allow for algorithms that run in run times vastly smaller than the best classical algorithms.
>>53217661
Very good explanation by this guy. Allow me to try and faggot it up
instead of a string of bits being 1010101, it is simultaneously every combination of 1s and 0s, allowing quantum computers to reach solutions much faster
Qubits
>>53217661
So bits are both 1 and 0 until you read them then they're either 1 or 0?
Why do you keep posting this azn?
>>53217595
cosmic rays and broken time-space
yeah but how could you code like that?
>>53219340
Kind of, since they exist in both positions this allows for branching algorithms and fractals to reach a solution much faster because everything is running at once. Once the algorithm is finished, then the observer effect collapses the it into the solution and outputs it.
>>53219482
if you influence a butterfly to flap its wings a certain way at some point in the future, it's already happened.
>>53219482
Branching algorithms
>>53219340
You basically ramp them down from superposition to classical bits yes.
do these computers exist or is it just a theoretical thing?
>>53219561
they're in production.
the equivilent moore's law is doubling the qbits every 12 months, I believe.
>>53219561
Nasa has them.
>>53219597
can you link any sources where I can learn more about quantum computing, that doesn't require a masters degree to understand it?
>>53217595
They don't. It's purely hypothetical.
>>53217661
Good.
>>53219276
No.
>>53219340
No, depending on the particle that's entangled, it could be facing any direction but can only be checked in one or two directions.
>>53219482
Difficultly.
I've see a CLI that does quantum programming, but didn't understand what was going on
>>53219561
Yes.
>>53219654
https://m.youtube.com/user/frameofessence
Videos for fun.
>>53219649
Either Google.
>muh algorithms blah blah blah
The only question that matters is: can it play games?
>>53219727
yes.
and no.
until you see it.
>>53219727
GTA5?
>>53219727
Or chess?
>>53217595
It runs gentoo
>>53217661
Now explain it like I'm a 10 year old
>>53219276
>>53219340
Also the quantum bits have a certain probability to collapse into each classical bit when observed.
>>53219482
Just like there are electronic gates for classical bits, there are quantum gates for quantum bits. The neat thing is that you can represent qbits as vectors and qgates as matrices and the application of a gate as matrix multiplication. You can then just use linear algebra to figure out the right quantum circuit for your problem.
>>53219649
So what is quantum computing supposed to do exactly? Query databases at enormous speeds?
You can't read the superposition of a qubit without observing it multiple times and getting the average state, right?
Tfw u will never quantum tunnel into anime
Great Intro:
Quantum computing for the determined: http://www.youtube.com/playlist?list=PL1826E60FD05B44E4
>>53219561
Only at an almost-proof-of-concept level. There are still physicists who believe they fundamentally cannot exist in a form that allows for computation faster than classical algorithms, but as time goes on, that number becomes fewer and fewer. Basically, it's been reduced to an engineering and materials science problem, not a design problem.
>>53219597
12 months is generous
>>53219654
He writes at a level that oscillates between "I assume pop-sci levels of understating" and "I assume you are a computer scientist or physicist with a masters", but Scott Aaronson's blog is a good source for keeping up to date with this stuff. He's one of, if not the leading researcher in the CS theory side of quantum computing.
http://www.scottaaronson.com/blog/
>>53219727
No. Basically, the chances of quantum computers ever existing in our homes, in our lifetimes, are nil. There is that whole thing about the director of IBM or whoever estimating the world in the future would need about 4 computers, but according to our current understanding, you won't be able to run any practical workloads faster than what you currently can on a highly optimized classical chip. Right now, there's only a couple things we *know* QC will be better at than classical computing (Namely, simulating quantum effects, and cryptanalysis. There are also people working on cryptographic mechanisms that use quantum effects for greater security, but I'm a crypto person by trade and I find the line of research unlikely to be fruitful).
>>53219820
That kind of was me explaining it in highly simplified terms. You can't really understand the idea without both a basic understanding of computational theory and quantum mechanics. The most bare-bones I can get is "some things compute faster when you calculate using 'probabilities' of the numbers involved instead of the actual numbers."
>>53219561
They actually exist but only in laboratories.
I think the record so far is that a quantum computer in a lab was able to use Shor's algorithm to factorize the number 6 into 3 and 2.
Do our brains use quantum mechanics in some way?
>>53219850
>So what is quantum computing supposed to do exactly?
I know it can do stuff like factorizing integers in a split second, or solving the discrete logarithm problem.
tl;dr all our crypto would be fucked up the arse
Database searching is not really a computational problem, it's a storage problem - and storage access will still be the bottleneck here.
>>53219931
No, our brains work on synapses that have more or less use on them creating weaker and stronger memories. Our brains are actually chemical as opposed to quantum or silicon, also there is no limit to how many neurons/connections we use simultaneously.
A very different thing to anything we've created, only ever heard of people with lots of neurology research but no computer engineering equating them.
I bet 5 dollahs that intelligence agencies already have working quantum computers fucking shit up, it's just classified like any new kind of tech.
>>53219959
>I know it can do stuff like factorizing integers in a split second, or solving the discrete logarithm problem.
...and apparently, that's pretty much where it stops
https://en.wikipedia.org/wiki/BQP#Quantum_computation
>>53219931
Our brains use quantum mechanics in the sense that everything in the universe uses quantum mechanics.
If you're asking how exactly our brain computes things, the answer is most likely going to be “we don't really know”.
>>53219921
out of date
>>53219986
>>53219959
Yeah its a crypto fuck mostly.
We'll encrypt with classical computers, because they're cheaper for the next 50-100 years, but they'll crack anything with their billion dollar quantum computer.
Fortunately your local cop shop won't have one (the people investigating YOU).
>>53220004
Plenty of people understand brains, just not in a way to reproduce one without cloning. People don't understand brains in a way to manipulate them like computers though.
>>53219850
>Query databases at enormous speeds?
Almost certainly not. We're working on entangling things on the level of *bytes* right now, forget shit the size of DB queries, classical silicon will almost certainly always be faster (or rather, cheaper, but in practice that's often the same thing).
>You can't read the superposition of a qubit without observing it multiple times and getting the average state, right?
You can never read a qubit without collapsing it. Quantum algorithms often involve repeating sub-computations because of the inherently probabilistic nature of things, so that you can say "this sub computation will give us this desired value with this probability, so if we repeat it enough, we can find the desired value". Generally, these sub-computations lie well within NP so you can just check to see if it gave you what you wanted.
>>53219921
56153 is currently the record
>>53219931
Nobody knows for sure yet, because consciousness isn't fully explained, but the leading thought right now says "no, probably not."
>>53219959
>tl;dr all our crypto would be fucked up the arse
all deployed asymmetric crypto, yes, but not all deployed symmetric crypto and not all asymetric crypto designed. I'm a grad student who does crypto stuff, and other people in my research group work on exactly this problem, which is how I know a little about it.
Is it possible to simulate a quantum computer using classical computing?
>>53220130
probably.
and probably not.
you'll just have to see.
>>53220130
Yes, the probabilistic Church-Turing Thesis still holds as far as we know. It would just be much, much slower than running it on a classical computer.
>>53220042
>We'll encrypt with classical computers, because they're cheaper for the next 50-100 years, but they'll crack anything with their billion dollar quantum computer.
The image of the future is not quite that dystopian actually.
It's true that some important CURRENT algorithms (pfac, dlog, ecc etc) will be fucked.
But all that means is that we will have to move on to quantum-safe algorithms instead.
https://en.wikipedia.org/wiki/Post-quantum_cryptography
>>53219895
>That kind of was me explaining it in highly simplified terms. You can't really understand the idea without both a basic understanding of computational theory and quantum mechanics. The most bare-bones I can get is "some things compute faster when you calculate using 'probabilities' of the numbers involved instead of the actual numbers."
that actually does help if the person in question has a more mathematical background from which they would know about asymptotes and how you find the curvature of a function leading up to them
>>53220265
The problem being that PQC isn't deployed right now. And this is a very big problem, the magnitude of it depending on how soon you think these machines will be feasible.
Think about it:
We assume that there are no efficient QC exists right now. So we're fine, right now.
But almost by definition, encryption doesn't exist at a single point in time. If I can send an encrypted message that can't be broken today, that's a minimum of security provided, yes, but if it can be recorded then broken tomorrow, that doesn't do me much good, because I presumably want all of my messages that are secret today to also be secret tomorrow.
So how far in the future do you care about your messages being secret? A year? Five years? A decade? Twenty years? Obviously, it depends on your threat model (my credit card number will be expired by then, but my 4chan posts could still be incriminating). So it's not good enough to say that we can move to PQC once QC becomes feasible.
>>53219561
NSA already has one that they use to crack AES256
>>53220392
Fair point, which I think makes it all the more important that we need to hurry up PQC research ASAP.
>>53220445
Lol no. Raw AES isn't known to be subject to any quantum attacks outside of the typical grover's advantage (runs in the square root of a typical brute force), which means AES256 is as strong in a quantum settings as AES128 is in a classical setting. AES128 is theoretically down to 64 bits of security in a quantum setting, but because of how slow and inefficient real QCs will be, idk how realistic that is.
>>53220457
oh indeed, even the NSA has said as much
I'm bored, so I'm going to write some up some basic ideas behind QC. Bear in mind, this isn't my area of expertise, all of this is just based on seminars my group has held, so take it with a grain of salt.
All classical computation, so everything you do on your computer or write out with a pen and pencil, can be represented using operations on bits, 1s and 0s. Any problem you want to solve using math on these bits, there is a limit to how few steps your algorithm can take to solve it. Sometimes we can prove what this limit is, many times we can't, but the limit always exists (e.g. we can't compute anything in less than 0 steps, obviously).
So the quantum universe, as we all know, is weird. So things get represented differently.
|0> and |1> represent the qbits corresponding to classical 0 and 1, respectively. We call the representations of these numbers "kets".
As a shorthand, we represent the contatenated kets |1>|0>|1> as the single ket |101>, etc..
Now, time for shit to get weird.
Because these qbits are quantum, they exist in "superposition," which can be thought of as existing in multiple states at the same time, or as a kind of "probability" (though not quite).
Every single qbit in superposition can fundamentally be represented as:
a|0> + b|1>, where |a|^2+|b|^2=1
Here, we refer to a and b as the "probability amplitudes" or just "amplitudes" of 0 and 1, respectively. These are kind of like probabilities, only they are complex numbers (a real number plus an imaginary number) instead of real numbers. In fact, if we square the magnitude of either vector, we get the probability of that value (i.e. |a|^2 is the probability of the qbit being 0, |b|^2 is the probability of the qbit being 1, which is why |a|^2+|b|^2=1 makes perfect sense).
continued
>>53221259
So then you might ask, if we know the probability, why even bother with all this quantum, probability amplitude, complex number nonsense? Because, when we run computations that would add, multiply, or otherwise modify the "probability" of these qbits, they instead operate on the amplitudes. Which means we can use the magic of complex numbers to do things like cancel out junk values.
Those are the major driving ideas. If you have any questions about wtf I'm talking about, go ahead and ask. But, assuming you do understand the above, we can take a look at some work that was published this month on breaking certain symmetric crypto schemes (like Fiestel networks, which are used to construct DES and other systems) using quantum algorithms. Pic related. Here, we see a quantum algorithm called "Simon's algorithm," that has been around for a while now, but the authors just found ways to use on these crypto systems. See if you can follow along how it works, just taking the Hadamard transform thing on faith. Assuming you know the neccessary set and function notation (if you don't, feel free to ask), and a little linear algebra, it's not too hard to follow along and see what they're doing.
Full paper here: http://arxiv.org/pdf/1602.05973.pdf
Congradulations, if you followed along with that, you can read the current bleading edge on some cryptanalysis research.
>>53221259
>>53221282
Good god, should have run spell check on that before I posted it. Oh well, deal with it.
>Quantum Cryptography
Just think for a second about how sci-fi this phrase is. I am really enjoying this!
>>53221259
>>53221282
Your introduction of the notation was a bit too fast for me. Some questions:
You mentioned something being represented using complex numbers, but it's not quite clear from the context what exactly you are referring to.
In a|0> + b|1>, are ‘a’ and ‘b’ both complex numbers? So is this like a complex-complex number system, where the complex magnitudes themselves again form a magnitude of 1?
You introduce notation like |101> but then gloss over what this really means. What would a|101> be?
>>53221428
Also, what does a|0> even mean? You've only ever clearly defined what |0> means: the qubit corresponding to the classical bit 0.
If ‘a’ is some sort of metavariable (of what type?), then is a|0> just a shorter version of a · |0> with some implicit operation ·? What is this operation?
What operations are defiend on qubits? What does a|0> + b|1> even mean? Like, how is + defined?
What would a|101> + b|010> be?
Neat
>>53221428
>>53221471
>In a|0> + b|1>, are ‘a’ and ‘b’ both complex numbers?
Yes.
>So is this like a complex-complex number system, where the complex magnitudes themselves again form a magnitude of 1?
The sum of the squares of the magnitudes sum to 1.
>Also, what does a|0> even mean? You've only ever clearly defined what |0> means: the qubit corresponding to the classical bit 0.
Yeah, this is the part that's hard to understand. "a" is the "probability amplitude". It soooort of represents the likelihood of you seeing that particular value if you measured it, but it's really just an abstract value (which we can use to calculate the actual probability). Let's pretend that there are no complex numbers involved, only probabilities. Then a|0> corresponds to "there's a probability of a that the qbit is 0". So if it was probabilities, that would imply that there is also a "(1-a)|1>" term that is being added as well, so that you end up with a total probability distribution summing to 1. But it's quantum, so it's not probabilities, it's complex vectors. So if we have a|0>, then we must have some value b in b|1>, such that |a|^2+|b|^2=1. So the probability of the bit being 0 is |a|^2 etc.
>You introduce notation like |101> but then gloss over what this really means. What would a|101> be?
Yeah I realized after posting that I didn't give this enough detail. a|101> is just the same thing, only with the concatenation of three bits. So let's say that there's a 3 bit "variable" or "register" or whatever. If we have a|101>, the amplitude corresponding to that variable containing "101" is a. There will be other values, call 'em a_2, a_3, ..., a_8, that are the amplitudes corresponding to the other possible values of those 3 bits.
>>53222526
continued
>>53221428
>>53221471
>What operations are defiend on qubits?
Uhh it gets a little more complicated here. You can, if you try, define all operations you can do on normal bit strings, if you fudge things a bit. But there are some special rules for qbits you have to take into account. The biggest ones being 1. any time you measure or copy the state of a qbit, it collapses to one of the "classical" bit strings 2. you cannot perform any operations that destroy any information; all operations must be reversible. I can show some examples if you'd like.
>What would a|101> + b|010> be?
Unless one of those vectors (a or b) is 0, that's as simplified as you can get. If you measure the bits at the end of this operation, you will see the string "101" with probability |a|^2, and "010" with probability |b|^2. Now, if you had a|101> + b|010> + c|010>, that you could turn into a|101> + (b+c)|010>, since the magnitudes combine for the possible bit string 010.
>>53222526
>The sum of the squares of the magnitudes sum to 1.
This equation is somewhat interesting.
Since complex magnitude is itself defined as |x+yi| = √(x2+y2), and given a = x+yi, b = z+wi the equation
|a|2+|b|2=1 becomes
√(x2+y2)2 + √(z2+w2)2 = 1
or just
x2+y2+z2+w2 = 1
Does that mean you can represent a qubit system of a|0> + b|1> as some sort of weird four-dimensional analog of the complex unit circle?
>>53222526
>If we have a|101>, the amplitude corresponding to that variable containing "101" is a. There will be other values, call 'em a_2, a_3, ..., a_8, that are the amplitudes corresponding to the other possible values of those 3 bits.
Ah, that makes sense!
Can I think about it this way, that when we're talking about a 3-qubit system, we're talking about manipulating 8-vectors of (a_1, a_2, a_3 ... a_8) (such that these 8-vectors have the property of their square magnitudes all adding up to 1) ?
>>53222589
And fuck 4chan for transforming the square symbol into just the number 2
Not well versed in complex numbers so only getting parts of it, but this is one of the best threads on /g/ in a while
>>53222589
>Does that mean you can represent a qubit system of a|0> + b|1> as some sort of weird four-dimensional analog of the complex unit circle?
I haven't thought about it too hard, but yeah, my guess is that you could.
>>53222623
>Can I think about it this way, that when we're talking about a 3-qubit system, we're talking about manipulating 8-vectors of (a_1, a_2, a_3 ... a_8) (such that these 8-vectors have the property of their square magnitudes all adding up to 1) ?
Yes, that's exactly correct. And once you measure the 3qbits, one vector becomes 1, and the rest become 0 (i.e. the state collapses).
>>53222676
Complex numbers are just vectors with a couple special rules (namely, i*i = -1), once you play with them a bit you realize they're nothing that special.
>>53223054
>I haven't thought about it too hard, but yeah, my guess is that you could.
>Yes, that's exactly correct. And once you measure the 3qbits, one vector becomes 1, and the rest become 0 (i.e. the state collapses).
I'm thinking about this some more. When I think of a sum of squares being equal to 1, I think of a hypersphere (in some dimension).
So really, the situation we have is that ket superpositions (is that what you'd call them?) are points on some hypersphere, where this hypersphere has an even number of dimensions?
e.g. in the case of a|00> + b|01> + c|10> + d11>, every possible configuration is a point on an 8-dimensional hypersphere (such a hypersphere being described by the subset x_1^2 + x_1^2 + ... + x_8^2 = 1)
Now here's where I'm thinking this may all connect: I saw in the video that you represent qubit superpositions as vectors pointing in some direction on a sphere. When I think of spherical directions, I think of quaternions.
Quaternions are essentially just 4D vectors which embed a rotation, and 1-qubit superpositions are essentially just points on a 4-sphere - i.e. they both have the same dimensionality.
Is there greater significance to this, or is it just a coincidence?
>ket superpositions (is that what you'd call them?)
Again, I'm just an outsider on this stuff, but my impression is that "ket" is just the notation, that it would be qbit superposisions or something like that.
>Is there greater significance to this, or is it just a coincidence?
No idea. But the reasoning seems pretty solid. Quick google search gives this paper on the relationship between the two:
http://www.ejtp.com/articles/ejtpv5i19p1.pdf
>>53223487
What are some good entry-level resources for learning about this stuff?
I tried searching for some talks on youtube but they never go into the mathematical details.
(Why does every talk, presentation or show always promise to “stay light on mathematics”? It's annoying, that's the bit that's actually interesting)
>>53224163
If you want the math, you basically have to go to the papers. Talks are generally constructed as "here's why you should read the paper I wrote," and will therefore not go into any of the specific math details, since they figure if you care, you'll, well, read the paper. I'm in a bit of a privileged position in that I can just raise my hand and ask at the end of the talk when I don't understand something. I don't know where I would even begin to look, other than searching google scholar for
"survey" AND "quantum computing"
or something to that effect. Sorry I'm not of more help.
>>53224229
There's a lecture on QC at my university's CS department, I guess I might go check that one out. (I need the credit either way)
