The world is quantum mechanical, damnit, and so (the party line goes) it shouldn’t be surprising if we find that a theory of computation based on quantum theory is more elegant than one based on machines whose concept of reality is so restrictive as to not allow cats both alive and dead. Okay, so we can say this half in jest, half seriously, but does it really hold any water? In order to solve this question of asthetics (joke about mathematics deleted), I propose that we hold a Quantum versus Classical beauty contest. Now since quantum computers are at least as powerful as classical computers, we can’t just say that an algorithm is better because it has a better runtime or better use of space, etc. Instead we need to use our artistic taste, i.e. pretend we have a clue about what it means for a result to be elegant (and yes, that was a dig at a certain popular science book đŸ˜‰ )
Round 1
So I propose we perform this artistic measuring with a quantum versus classical exponent SMACKDOWN! (the exclamation mark is a part of the word.) Consider, for example, the recent quantum algorithm for evaluating a NAND tree (here and here with an explanation by the traveling complexity theory salesman here. Also the awesome NAND formula paper here) This quantum algorithm has a running time of [tex]$O(N^{1/2 + epsilon})$[/tex]. Now compare this with the best and optimal classical algorithm for this problem. The result? [tex]$O(N^{0.753 dots})$[/tex] where [tex]$0.753 dots approx log_2(1+sqrt{33})-2$[/tex]. Bleh. Round One of the Quantum Versus Classical Exponent SMACKDOWN! most certainly goes to the quantum world. One half is certainly better than something which is has both a logarithm and a square root of thirty three!
Round 2
But ha, say the classical complexity theorists. What about Grover’s problem? Sure in this unstructured query search the quantum world achieves a speedup from [tex]$O(N)$[/tex] classically to [tex]$O(N^{1/2})$[/tex] quantum mechanically, but look at your exponent. One half? Who the hell ordered one half. I mean if you had gotten log of N or even constant, then you would have something to brag about. But a square root speedup. Who ordered that? Round two of the Quantum verus Classical Exponent SMACKDOWN! most certainly goes to the classical world were weird square root speedups are not ubiquitous for straightforward unstructured query searches.
Round 3
To be continued!
O brave new quantum world!
one word: no cloning theroem!
That’s three words and an exclamation mark.
whatever. So…. Hardamard
Just one, right?
(well, at least, *I* find them ugly)
oosp, I can’t edit my posts… I mean Hadamard of course.
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.
“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? đŸ˜€
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.
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!
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.”
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.
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?