Comments on: Quantum versus Classical: Exponent SMACKDOWN! http://dabacon.org/pontiff/?p=1464 Theoretical Musings Thu, 09 Sep 2010 14:06:56 +0000 hourly 1 http://wordpress.org/?v=3.0.1 By: Dave Bacon http://dabacon.org/pontiff/?p=1464#comment-188755 Dave Bacon Tue, 03 Jul 2007 03:10:49 +0000 http://dabacon.org/pontiff/?p=1464#comment-188755 Hey, no fair bringing in a classical deterministic model. In any case, it would have to be a tie, wouldn't it, since classical deterministic machines can be simulated on a quantum deterministic machine which just never uses superpositions? Hey, no fair bringing in a classical deterministic model. In any case, it would have to be a tie, wouldn’t it, since classical deterministic machines can be simulated on a quantum deterministic machine which just never uses superpositions?

Like or Dislike: Thumb up 0 Thumb down 0

]]> By: fred http://dabacon.org/pontiff/?p=1464#comment-188056 fred Fri, 29 Jun 2007 21:52:36 +0000 http://dabacon.org/pontiff/?p=1464#comment-188056 In Round 1, I think classical deterministic beats out both quantum and classical randomized, as the running time is Theta(N) -- exponent 1. I imagine classical deterministic wins most of these competitions. In Round 1, I think classical deterministic beats out both quantum and classical randomized, as the running time is Theta(N) — exponent 1. I imagine classical deterministic wins most of these competitions.

Like or Dislike: Thumb up 0 Thumb down 0

]]> By: Wim van Dam http://dabacon.org/pontiff/?p=1464#comment-163521 Wim van Dam Fri, 16 Mar 2007 22:20:23 +0000 http://dabacon.org/pontiff/?p=1464#comment-163521 Meanwhile, in a different ring: "And now, ordered searching: Classical... log N, nice and quick, maybe a bit rough around the edges for non powers-of-two, but a very, very good effort by Classical." "Let's see how Quantum does... Err, well, is it also going to be log N?, hmm, no, maybe 1/2 log N then? Yes? Yes? No!! Odd. It is really hard to see what is going on here dear viewers; Quantum seems to be stalling for time to figure out how to get out of this mess... Is it going to be 1/pi log N? That would probably be a win for Classical, but some of the jury members might think otherwise... Oh, well, maybe that we know more when we are back after these messages." Meanwhile, in a different ring: “And now, ordered searching: Classical… log N, nice and quick, maybe a bit rough around the edges for non powers-of-two, but a very, very good effort by Classical.”
“Let’s see how Quantum does… Err, well, is it also going to be log N?, hmm, no, maybe 1/2 log N then? Yes? Yes? No!! Odd. It is really hard to see what is going on here dear viewers; Quantum seems to be stalling for time to figure out how to get out of this mess… Is it going to be 1/pi log N? That would probably be a win for Classical, but some of the jury members might think otherwise… Oh, well, maybe that we know more when we are back after these messages.”

Like or Dislike: Thumb up 0 Thumb down 0

]]> By: Scott http://dabacon.org/pontiff/?p=1464#comment-163500 Scott Fri, 16 Mar 2007 20:34:56 +0000 http://dabacon.org/pontiff/?p=1464#comment-163500 Collision problem: Classical N^{1/2}, quantum N^{1/3}, and it's a TIE! Element distinctness: Classical N, quantum N^{2/3}, and CLASSICAL WINS! Local search: Classical 2^{n/2} n^{1/2}, quantum 2^{n/3} n^{1/6}, and it's a TIE! Game trees with branching factor of 3: Classical something weird, quantum N^{1/2}, and QUANTUM WINS! Game trees with branching factor of 4: Classical something else weird, quantum N^{1/2}, and QUANTUM WINS! Game trees with branching factor of 5: Classical yet another weird thing, quantum N^{1/2}, and QUANTUM WINS YET AGAIN! LADIES AND GENTLEMEN, QUANTUM IS CLEANING THE HOUSE! Collision problem: Classical N^{1/2}, quantum N^{1/3}, and it’s a TIE!

Element distinctness: Classical N, quantum N^{2/3}, and CLASSICAL WINS!

Local search: Classical 2^{n/2} n^{1/2}, quantum 2^{n/3} n^{1/6}, and it’s a TIE!

Game trees with branching factor of 3: Classical something weird, quantum N^{1/2}, and QUANTUM WINS!

Game trees with branching factor of 4: Classical something else weird, quantum N^{1/2}, and QUANTUM WINS!

Game trees with branching factor of 5: Classical yet another weird thing, quantum N^{1/2}, and QUANTUM WINS YET AGAIN! LADIES AND GENTLEMEN, QUANTUM IS CLEANING THE HOUSE!

Like or Dislike: Thumb up 0 Thumb down 0

]]> By: osias http://dabacon.org/pontiff/?p=1464#comment-163476 osias Fri, 16 Mar 2007 18:56:48 +0000 http://dabacon.org/pontiff/?p=1464#comment-163476 Just kidding, I understand you're talking about results and I'm still trying to cope with the "ugliiness" I sense while trying to learn. One of the few things I learnt until now was the Deutsch-Jozsa algorithm, and I agree ONE single query is A LOT prettier than 2^(n-1)! I almost started to like Hadamards because of that. Almost. Just kidding, I understand you’re talking about results and I’m still trying to cope with the “ugliiness” I sense while trying to learn.

One of the few things I learnt until now was the Deutsch-Jozsa algorithm, and I agree ONE single query is A LOT prettier than 2^(n-1)!

I almost started to like Hadamards because of that. Almost.

Like or Dislike: Thumb up 0 Thumb down 0

]]> By: osias http://dabacon.org/pontiff/?p=1464#comment-163472 osias Fri, 16 Mar 2007 18:49:46 +0000 http://dabacon.org/pontiff/?p=1464#comment-163472 "<i>it is also true for classical probabilistic computers</i>" Oh, well, I also find classical probabilistic ugly, I wish only deterministic algorithms could exist... But you're rigth, lemme think about another thing. ... Commenting on the bra-ket notation is allowed? :D “it is also true for classical probabilistic computers”

Oh, well, I also find classical probabilistic ugly, I wish only deterministic algorithms could exist… But you’re rigth, lemme think about another thing.

…

Commenting on the bra-ket notation is allowed? :D

Like or Dislike: Thumb up 0 Thumb down 0

]]> By: Dave Bacon http://dabacon.org/pontiff/?p=1464#comment-163465 Dave Bacon Fri, 16 Mar 2007 18:35:12 +0000 http://dabacon.org/pontiff/?p=1464#comment-163465 The no cloning theorem doesn't differentiate because it is also true for classical probabilistic computers. I think I'd take a Hadamard over a stocashtic matrix with all 1/2's anyday. At least the former has a change of returning to identity. The no cloning theorem doesn’t differentiate because it is also true for classical probabilistic computers. I think I’d take a Hadamard over a stocashtic matrix with all 1/2′s anyday. At least the former has a change of returning to identity.

Like or Dislike: Thumb up 0 Thumb down 0

]]> By: osias http://dabacon.org/pontiff/?p=1464#comment-163464 osias Fri, 16 Mar 2007 18:34:20 +0000 http://dabacon.org/pontiff/?p=1464#comment-163464 oosp, I can't edit my posts... I mean Hadamard of course. oosp, I can’t edit my posts… I mean Hadamard of course.

Like or Dislike: Thumb up 0 Thumb down 0

]]> By: osias http://dabacon.org/pontiff/?p=1464#comment-163463 osias Fri, 16 Mar 2007 18:30:34 +0000 http://dabacon.org/pontiff/?p=1464#comment-163463 whatever. So.... Hardamard Just one, right? (well, at least, *I* find them ugly) whatever. So…. Hardamard

Just one, right?

(well, at least, *I* find them ugly)

Like or Dislike: Thumb up 0 Thumb down 0

]]> By: Dave Bacon http://dabacon.org/pontiff/?p=1464#comment-163460 Dave Bacon Fri, 16 Mar 2007 18:23:54 +0000 http://dabacon.org/pontiff/?p=1464#comment-163460 That's three words and an exclamation mark. That’s three words and an exclamation mark.

Like or Dislike: Thumb up 0 Thumb down 0

]]>