00:00:07 Hm. Does that mean 704 bits? 00:00:14 Seems to. 00:00:37 And the number is 74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359. 00:00:54 Try 3. I've got a good feeling that it's some number times 3. 00:01:33 Nope, it's congruent to 1 mod 3. 00:01:43 Well, I'm out of ideas. 00:02:14 Okay. Choose a random number from 1 to RSA-704. 00:02:14 So to break this one, you'd need a 704-qubit register, right? Pfft, good luck, hardware designers. 00:02:58 ...Well? 00:03:08 Uh... We already did 3. So... um... floor(pi * googol). 00:03:44 That's 101 digits, about the right size for one of the offending factors. 00:03:54 Probably not even prime, but since when is that MY problem? 00:04:17 Okay, the number is 31415926535897939206342872074089512377015178275785648855278065595809401623948916766946766405184258048. 00:04:28 DAMN! Even. 00:04:34 So, uh, forget that entirely. 00:05:00 No, we can still use it. 00:05:07 But this and that are coprime. 00:05:23 This and 3, or this and the RSA number? 00:05:31 This and the RSA number. 00:05:46 Now, f(x) = this^x mod that. 00:06:06 Do you know the period of that function? 00:06:31 Nope. 00:06:52 Oh. 00:07:09 Uh... wanna ask EgoBot? 00:07:27 Maybe... write a BF program. Or Glass. And wait 20 years or something. 00:07:39 We got time. 00:07:53 What if somebody else does it first? 00:08:20 Okay, I need you to create a register that contains everything from 0 to the RSA number minus one, all with equal positive probability amplitudes. 00:08:23 Then we use a different algorithm: find the guys who did it, then beat the crap out of 'em and take credit for the accomplishment. 00:08:45 I'll split the cash 100-0 your way, since odds are you're the one who's gonna be in charge of the beating. 00:08:56 And I wouldn't know what to do with the money. 00:09:07 But nobody's done it yet, and the RSA guys will probably know it's them before we will. 00:09:37 Okay then, back to the original plan. Um... crap. I'm gonna need a lot more RAM. 00:10:34 So... what's 1 over RSA-704? 00:10:43 Hmm? 00:11:15 The reciprocal. The probability. We can figure out the amplitude from that. 00:11:18 Oh. 00:11:43 The reciprocal is 1/74037563479561712828046796097429573142593188889231289084936232638972765034028266276891996419625117843995894330502127585370118968098286733173273108930900552505116877063299072396380786710086096962537934650563796359. 00:12:08 Approximately 1.3506657337204956e-212, that is. 00:13:30 Uh... huh. Is it too late to kill this process and just do a simple "Hello World"? 00:13:39 'Cause this could take a while. 00:13:50 Um... 00:13:55 Kill what process? 00:14:26 The quantum factoring algorithm. 00:14:44 It's not working nearly as well as I had hoped. 00:14:53 !ps 00:14:56 1 ihope_: ps 00:15:07 Not too late, then. 00:15:19 K then. 00:15:24 !kill irp 00:15:26 No such process! 00:15:43 Anyway, the probability amplitude you need is about 1.1621814547309278e-106. Initialize them to that. 00:16:00 !kill q-irp 00:16:02 No such process! 00:16:56 You need to be an IRC operator to do that. 00:17:26 Then I'll have to try the old exception-handling way. 00:17:32 Please stop trying to factor RSA-704. 00:18:00 Interrupt the running, and all that. ^^ 00:19:06 What if I don't want to stop? 00:19:35 Well, knock yourself out, but don't expect me to continue helping as a parallel processor. 00:19:58 But... the other chatters might complain. Or they would if they were still here. 00:20:08 * AndrewNP pokes the sleepy chatroom citizens. 00:23:35 * pikhq is poked 00:24:13 * AndrewNP is slapped with a sexual harassment class-action suit. 00:25:32 And statutory rape. 00:25:46 How old is AndrewNP? 00:25:50 20. 00:25:56 Yup :P 00:25:57 And two months. 00:26:04 But not that kind of poke... I think. 00:26:22 The courts don't care what kind of poke it was. 00:26:31 lol 00:26:42 Damn "justice" system. 00:27:16 Honestly, ONE body-fluid-stained corpse and they're all like "Ooh, Murder in the First Degree!" 00:27:31 :p 00:28:21 I mean, two or three, sure, I can understand. But doesn't everyone get a freebie? I think that's in the UN charter or something. 00:28:29 http://www.donotputthebaby.com/index.php?s=Knife 00:28:45 How hard does one have to try to kill someone in order for it to be considered attempted murder? 00:28:54 It doesn't count if I just want someone to die, does it? 00:29:02 That's attempted manslaughter X-P 00:29:10 Eh, you probably have to DO something at least. 00:29:18 Like, chase 'em with a knife. 00:29:49 Doing something that could have been fatal, but wasn't? 00:29:49 Here's an esolang for ya: http://www.donotputthebaby.com/index.php?s=Code 00:30:00 Probably. Like, you really really REALLY expected 'em to die. 00:30:18 Shooting 'em and just missing the heart, for example. 00:34:08 Well, let's try to factor 4 using Shor's algorithm. 00:34:14 Just for practice and all that. 00:35:41 So a = 1. The GCD thingy is 1... well, yeah, 1 is a factor of 4. 00:36:11 Let's say a = 3, since that's *not* a factor of 4. 00:36:32 Speaking of just wanting somebody to die ... 00:39:05 GregorR: Uh-oh. I'm sorry! :'( 00:40:02 Okay, so now we take .5|00>+.5|01>+.5|10>+.5|11> 00:40:17 .5^2 = .25, so that should work as the amplitude. 00:40:29 No, .5|00> + .5|10> + .5|20> + .5|30>. 00:41:03 Speaking of just wanting somebody to die ... :P 00:41:16 GregorR: Yes, what? Who do ye want dead? 00:41:25 He didn't say that. 00:41:35 Okay, fine. First register = 0-3, Second = 0. 00:41:40 Yep. 00:41:55 So then we take... 3^x mod 4, right? 00:41:59 Yep. 00:42:29 So we turn that into (|01> + |13> + |21> + |32>)/2, I think. 00:43:08 ...No, (|01> + |13> + |21> + |33>)/2. 00:43:13 Yeah, that's better. 00:43:51 Now Fourier transform that bad boy! 00:44:03 Er, inverse. Inverse Fourier transform. 00:44:36 ...How do I do that? 00:44:45 Damned if I know. 00:45:09 Oh, let's skip to the probability part. 00:45:28 You have to do the transform first, buddy. 00:45:50 Is there some sort of Introduction to Quantum Computing? 00:45:51 Do we? 00:46:11 Razor-X: well, you might wanna look at... something. Lemme see... 00:46:17 I think. Otherwise the numbers we're working with would be all wrong. 00:46:37 Razor: Actually, I promised a couple guys I'd write up a QC tutorial for 'em. 00:46:49 Razor: Do you want the physics behind it, or just the math and comp-sci part? 00:47:04 Well, you have to understand wavefunctions. 00:47:35 AndrewNP: Well, depends on how involved the physics is. 00:47:43 No, I don't have enough background for the wavefunctions. 00:47:54 Unless a wave function is a sine curve :D. 00:48:10 I thought the whole point of the bra-ket thingie was to abstract out the wavefunction? 00:48:17 Um, well... yeah. 00:48:21 Okay, skip that. 00:48:35 Now, instead of 0 and 1, we have |0> and |1>. 00:49:03 Awesome. 00:49:06 And we can use |0> and |1> as numbers, sort of. 00:49:08 Like 0 and 1, smilified. 00:49:17 Sort of, mmmkay. 00:49:27 And this time, instead of covering up a voltage, they stand for a whole crapload of physics. 00:49:56 We can add quantum states to each other, and we can multiply quantum states with numbers. 00:50:28 Essentially, you have to be able to turn it into something of the form a|0> + b|1>. 00:50:43 And |a|^2 + |b|^2 has to be 0. 00:51:08 So |0>*sqrt 2 + |1>*sqrt 2 is valid, but 2|0> isn't. 00:51:12 You mean, has to be 1. 00:51:17 Yes. 00:51:48 So you can have like... sqrt(2)|0> 00:51:55 Razor-X: so now that you understand everything, write me a qbf program. 00:52:04 Uh...... 00:52:25 Razor-X: well, no, because the square of the absolute value of the square root of 2 is 2. 00:52:42 Mmmm. Can someone make a TeX proof of this? >_>. 00:52:51 A TeX proof of what? 00:52:55 Errr, not proof. 00:53:03 But, it's hard to see without only ASCII on IRC. 00:53:15 (Note. I should be studying for my Statistics final. Do I care? No.) 00:53:22 Oh, wait, I meant |0>/sqrt 2 + |1>/sqrt 2. 00:53:36 So, uh ... |0> is divided by sqrt(2) ? 00:53:42 Yep. 00:53:51 But what value does |0> have? 00:54:05 |0> is just |0>. It's like a variable. 00:54:43 Alright.... 00:55:14 But then, since |0> is symbolysis for physics cr*p, then you can at most simplify to |0>/sqrt(2) ? 00:55:32 Well, |0> and |0>/sqrt(2) are different thinges. 00:55:50 Well, yeah... I understand that... 00:55:54 Yeah. Think of it as an ordered pair with |0> and |1> coordinates. 00:55:59 Ok. 00:56:16 What operations can you do to these |0> and |1> ? 00:56:43 Well... 00:57:12 There must be some repeatability in the operations to produce logic with them, no? 00:57:16 An example would be the Hadamard gate, which turns |0> into (|0> + |1>)/sqrt(2) and |1> into (|0> - |1>)/sqrt(2). 00:58:07 How do you perform logic, then? 00:58:22 With different gates, on a bit level? 00:58:24 Well, there's, say, the Toffoli gate, which is simply a logic gate turned quantum. 00:58:37 no 00:58:41 toffoli gate is not quantum. 00:58:50 it operates on regular bits. 00:58:56 Mmmmm. 00:59:05 The Toffoli gate leaves everything the same, except that it turns |110> into |111> and vice versa. 00:59:07 But the Toffoli gate IS reversible, one-to-one, which is what all quantum gates need to be. 00:59:31 Something about thermodynamics. Don't know, don't care. 00:59:37 Heh. 00:59:49 So there's no such thing as a ``Quantum Truth Table'' ? 00:59:55 A what? 01:00:14 Well, yes, but they're more complicated. 01:00:25 Quantum gates use a square matrix to describe the transformation. 01:00:37 How so? 01:00:54 Well, the outputs can be any quantum states, instead of simple bits. 01:01:45 ihope: Well, duh. ;) 01:01:45 But here, the quantum states are |0> and |1> ? 01:01:55 And combinations of them. 01:02:04 Yeah, those are just the base states. 01:02:12 The x and y, if you will. 01:02:38 You can also have things like (|0> + |1>)/sqrt(2). 01:03:21 So, all you can do is divide by sqrt(2) one or both of the quantum states? 01:03:31 Well... 01:03:48 There are also states like -|1> and |1>i. 01:04:09 Well, |1>-1 is the same thing as -|1> ? 01:04:10 Or 3/5 |0> + 4/5 |1> 01:04:11 The only rule for quantum states is that the squares of the absolute values have to add up to 1. 01:04:19 Ah. 01:04:31 Razor: It has to be in the form a|0>+b|1>. 01:04:38 Adding a constant is meaningless. 01:04:50 Oh! I see. 01:05:10 abs( a|0> ? b|1> )^2 = 1 ? 01:05:16 Trying to pastebin an explanation of matrix notation, but it's being slow >_< 01:05:18 Errr... 01:05:23 abs( a|0> + b|1> )^2 = 1 ? 01:05:30 abs(a)^2 + abs(b)^2 = 1 01:05:39 Ok. 01:05:51 And as ihope pointed out, a and b can be complex. 01:05:52 http://pastebin.ca/101581 < matrix notation 01:06:33 To use the quantum gate, you just have to multiply the state vector by the matrix. 01:07:01 For example, for a single qubit a|0>+b|1>, the state vector is [a,b]. 01:07:20 But, you would get a resulting matrix then, no? 01:07:28 Isn't the goal to get a resulting vector? 01:07:35 A vector times a matrix is a vector. 01:07:41 Oh, duh. Whoops. 01:07:43 And since the matrix is square, it'll be the same dimension. 01:07:51 Yeah, I see. 01:08:00 Ah, OK, so then these gates are scientifically designed to be possible? 01:08:09 Yep, something like that. 01:08:23 Don't ask me how. Maybe ihope knows? (If you care, that is.) 01:08:38 IIRC, at least a few exist in reality. 01:08:44 Well, what do you mean by "these gates"? 01:08:53 These matricies. 01:09:02 But which ones are "these" ones? 01:09:14 The ones that are used in QC. Hadamard, CNOT, and so forth. 01:09:36 Well, if they weren't actually possible, we probably wouldn't be using them. 01:09:53 There is one limitation, though. QC gates have to be "unitary" matrices. 01:10:15 Unitary? 01:10:29 Its conjugate transpose has to equal its inverse. 01:10:37 I don't know if there are any rules other than that they have to be unitary and they have to actually produce valid states. 01:10:57 * Razor-X decides to look up Matrix conjugate transposes. 01:11:45 Then, I gather there's a large-but-finite amount of states? 01:11:53 s/unitary/reversible/ 01:11:58 Technically it's infinite. 01:12:05 Oh. 01:12:14 Any two complex numbers that obey |a|^2 + |b|^2 = 1 are legal. 01:12:41 .... I'll assume that complex numbers can be states too :P. 01:12:46 Yep. 01:12:56 Mmmm. Doublethink. 01:13:01 Yeah. You could have 3/5i |0> + -4/5 |1>. 01:13:06 Anyhow, how does this fit into computing? 01:13:15 You can compute with these. 01:13:20 Well, the real magic happens once you get more than one qubit. 01:13:29 For multiple qubits, you have things in the form a|00> + b|01> + c|10> + d|11>. 01:13:44 But, can 4 qubits go into one gate? 01:13:46 And |a|^2 + |b|^2 + |c|^2 + |d|^2 = 1. 01:13:56 Razor-X: if it's a 4-qubit gate, yes :-) 01:14:14 Yep. 4x4 matrices = 2-qubit gates. 8x8 = 3 qubits. 01:14:20 And so on and so forth. 01:14:23 So the rules stay the same, just reversible and produces valid states? 01:14:30 Yep. 01:14:51 Is there any math to decrease the ``circuitry'' involved? 01:15:04 Like a K-map or something? 01:15:48 Um... 01:16:07 Well wait... because normal bits have two possible states, you can produce logic in the form of base-2 numbers..., if the number of possible states is infinite, you have base-infinite numbers??? 01:16:17 Nope, still base two. 01:16:28 The numbers are actually *probabilities*. 01:16:34 Oh :D. 01:16:55 That when you observe the bit or do something irreversible, the value will be |0> or |1>. 01:17:16 So... if you want a |1>, you want to get the probability for |0> as low as possible? 01:17:22 Yep. 01:17:26 Preferably to 0 :P 01:17:45 All the qubits in QBF start as (0,1), so that's easy :P 01:17:59 So that also chops down the number of possible states by a lot too, if you want totally probably states, no? 01:18:03 But if you want a |1>, you can just pull one out of thin air. 01:18:11 Razor-X: if you want what? 01:18:19 A |1> ? 01:18:27 Wait.... 01:18:33 *totally probable states 01:18:34 Blah. 01:18:49 Yeah. Part of the problem with QC is figuring out a way to make the correct answer the probable outcome. 01:18:53 Mind you, I believe that in QBF you can actually only achieve about six states ... 01:19:12 GregorR-W: what're those? 01:19:21 Figuring it out right now :P 01:19:22 Razor: 'Cause once you observe something, it stays in that state. It collapses to a pure |0> or |1>. 01:19:41 So, the goal of qubits is to apply a certain number of gates until the probability for a certain qubit becomes 1 and the rest 0? 01:19:47 AndrewNP: Yeah, I know. 01:19:55 OK, much more than six, but finite :P 01:19:58 Razor-X: well, sort of, yeah. 01:20:04 Sort of :P. 01:20:26 Well, you usually can't guarantee a 100% probability, but if you get a high figure and run the algorithm several times, you should get a pretty good idea of the answer. 01:20:36 What's the advantage of quantum computing over binary computing? 01:20:36 high *probability*. 01:20:47 (0, 1), (1, 0), (1/sqrt(2), 1/sqrt(2)), (1/sqrt(2), -1/sqrt(2)), (0, i), (i, 0), (0, -1), (-1, 0), (0, -i), (-i, 0), (i/sqrt(2), i/sqrt(2)), (i/sqrt(2), -i/sqrt(2)), (-1/sqrt(2), -1/sqrt(2)), (-1/sqrt(2), 1/sqrt(2)), (-i/sqrt(2), i/sqrt(2)) 01:20:49 Razor-X: doing lots at the same time. 01:20:55 Probably missed some :P 01:20:56 ihope_: Huh? 01:21:02 But, gtg 01:21:05 -!- GregorR-W has quit ("Chatzilla 0.9.73 [Firefox 1.5.0.2/0000000000]"). 01:21:47 Razor: The number of states that can be manipulated at once goes up exponentially with the number of qubits. 01:21:57 I see. 01:22:12 If you put something into a superposition of every basis state, then apply some function to it... 01:22:14 But, what's the advantage to the different number of states? 01:22:33 Each one represents a binary number. Like |01001>. 01:22:51 So with 5 qubits, you can apply the function to the range [0..31] simultaneously. 01:22:54 Aha! 01:23:03 I see. 01:23:21 Now the lightbulb goes off, and she becomes a believer. :) 01:23:21 What operations does QBF allow? 01:23:25 Er, on. 01:23:26 Hehehe. 01:23:50 And with QC, you can access some of the weirder parts of quantum physics. Like entanglement. 01:23:55 Hadamard gate, controlled-V gate, swap. 01:24:01 The bits don't have to be indpendent of each other. 01:24:10 Uh.... :P. 01:24:20 Using probabilities instead of those godawful magnitudes, let's say you have... 01:24:21 The Hadamard gate and controlled-V gates have their own matricies, I gather? 01:24:36 Razor-X: well, just don't thing of them apart. And yes, they have their own matrices. 01:24:54 10% |00> + 20% |01> + 30% |10> + 40% |11>. 01:25:15 100%! Woohoo! I can count! 01:25:21 Instead of two (|0> + |1>)/sqrt(2) that have to be the same, you can just have (|00> + |11>)/sqrt(2). 01:25:41 Better example, ihope. I yield to you. 01:25:45 So if the probability of two qubits is the same, they're considered to be the same qubit? 01:26:16 Well, when you have two or more qubits, you can't consider them in isolation. 01:26:38 In ihope's case, whatever the first bit is observed to be, the second bit will NECESSARILY be also. 01:26:55 Yeah, I understand. 01:26:59 In my case, observing one bit will alter the probability state of the other bit. 01:27:16 If you've taken a stats class, this should all be simple enough. ;) 01:27:18 Physically though, you can only view one of the two, no? 01:27:38 Nah, you can view any one of them. Ideally, at least. 01:27:45 At the same time? 01:28:12 Probably. And the probability of each outcome is determined, again, by the overall matrix. 01:28:22 Ah. Ok. 01:28:35 So for ihope, there's a 50-50 chance of seeing |00> or |11>. But you will NOT get |10> or |01>. 01:29:04 I see. 01:29:33 But if physically you only see one of the two, what's the point of them having the same probability other than to confuse? 01:30:13 Well, ihope's case is more to give you a feel of how it works. 01:30:23 Mmmkay. 01:30:33 I don't think it would occur in a practical algorithm. 01:31:01 Well, it doesen't seem *too* complicated... if that's all there is to it.... 01:31:20 At a very high, abstract, I-don't-care-about-the-very-complicated-physics level. 01:31:29 Yeah, the math concepts are pretty easy. The challenge is designing algorithms for it. 01:31:41 Seems like a perfect job for the Esolang community. 01:32:02 And, of course, there's the hardware level. They think 7 qubits is an accomplishment. They factored 15. 01:33:39 Razor: Yeah, that could be a good field of study. 01:33:57 Certainly more fruitful than "How many ways can we encode Brainf***?" X-D 01:34:13 Hahahaha :P. 01:34:34 Well, 7 qubits is better than binary for sure. 01:34:35 like a perfect job for the Esolang community. 01:34:35 [20:31] And, of course, there's the hardware level. They think 7 qubits is an accomplish 01:34:54 Whoa. Did I paste that? 01:35:00 Yeah, you did :P. 01:35:16 Sorry. Need to not play with ctrl-C while this window is open. ^^;;; 01:35:23 Heh. 01:35:31 Is the QBF interpreter ready yet? 01:35:48 Wait a second... hmmmm... 01:35:51 How does QBF syntax look? 01:36:05 A lot like BF. 01:36:13 I gathered that much :P. 01:36:18 But with ! and % and & and such. 01:36:24 But I mean..., you don't have a ``tape'' here do you? 01:36:48 It works on a "tape" of qubits. 01:36:53 Yep. 01:36:58 All initialized at |0> ? 01:37:06 All initialized to |1>. 01:37:09 Ah. 01:37:16 How many qubits at once? 01:37:18 ihope: Any reason for that instead of |0>? 01:37:19 Just one? 01:37:42 Well, the qubits can be entangled, as in a single register. 01:37:46 AndrewNP: well, it might actually be impossible to create a NOT gate. 01:38:21 Oh right. 'Cause of the controls. Do they make "inverse-controlled" gates? 01:38:27 But it's possible to get a CNOT, so it starts with |1> so people can use that. 01:38:56 And they don't make gates wholesale. :-) 01:39:21 Heh. I meant, like, physically and mathically speaking. 01:39:26 So You can invert one way but not the other? 01:39:29 Mathically :P. 01:40:08 Well, controlled gates only work if there's a |1> bit somewhere. 01:40:30 Like, if bit one = 1, do THIS to bit two. 01:40:43 It's a convenient way to entangle two qubits. 01:42:13 Entangle? 01:42:16 :P. 01:42:27 Make their states codependent. 01:42:36 How would you do that? 01:42:44 By changing the probabilities? 01:43:14 Pretty much. Controlled gates change |10> and |11> without touching |00> or |01>. 01:43:47 Well, if we have multiple qubits, then we use |00> and such as basis states instead of |0> and such. 01:44:02 Mmmkay. 01:44:11 I feel happy with my now-new-knowledge in fancy lingo. 01:44:26 And somewhat-simple math. 01:45:24 The problem with bra-ket notation is that it can be tricky to tell | and 1 apart :- 01:45:32 s/:-/:-)/ 01:45:52 My font sees it fine, heh. 01:46:25 How is input handled? 01:46:34 In QBF, or just in general? 01:47:01 Both :). 01:47:04 Razor-X: I mean when writing them down. I tend to write both the same, except with | a bit longer. 01:47:17 Ah. 01:47:29 I write the 1 with the extra appendage up top. 01:48:13 In QBF, you take a classical bit from cin and write it to the current qubit. Right? 01:48:29 AndrewNP: that's one way of doing it. 01:48:33 So then, you're manipulating 8 qubits, I imagine? 01:48:44 Razor-X: why 8? 01:48:59 Well... ASCII input.... 01:49:18 Oh. 01:50:38 Eh, I guess you could handle it like that BIT language, where it reads in the character 1 bit at a time... 01:50:53 The only problem is, since it's ASCII, you'd never get a 1 for the high bit. 01:51:27 If you give it Unicode, you could. 01:51:52 Or if you only limit it to 7 qubits.... 01:52:02 (Which seems physically possible, at least.) 01:52:58 Well, I don't think you have to limit the qubits -- since you can write the input one bit at a time. 01:53:18 Like BoolF. 01:53:38 Right. Maybe you could just discard every 8th bit...? 01:55:08 Well, that would also be quite painful. 01:55:17 More so than it already is with matricies :P. 01:56:15 True. I guess you could just live with the always-zeroed bit. 01:56:34 The bigger concern would be actually writing it. Since you'd probably have to observe and collapse the qubit first. 01:57:05 So that it'd be in a pure state that could be flipped. 01:57:06 Um... 01:57:22 If you want to write to a qubit, discard it and get a new one :-) 01:57:42 But what would that do to the existing state vector? 01:57:52 I wanna make sure whatever happens is physically possible. 01:58:02