modulereview larsen <table border="0"> <tr> <td width="50%">&nbsp;</td> <td width="50%"><blockquote> &lt;[larsen]&gt; I think I'll add a disclaimer...<br> &lt;[larsen]&gt; <i>"No cat has been hurt to write this review"</i><br> &lt;[neshura]&gt; lol<br> &lt;[neshura]&gt; IMPOSSIBLE<br> <p> &lt;[larsen]&gt; hi neshura, I didn't noticed you<br> &lt;[larsen]&gt; :)<br> &lt;[neshura]&gt; now that you have noticed, bet you can't tell what my velocity is<br> <p align="right">-- Two monks on IRC :)</p> </blockquote> </td> </tr> </table> <h2>Quantum computing in a nutshell</h2> One of the possible formulations of Church-Turing's thesis (actually it's not equivalent: is a reinforcement also known as <i>thesis of sequential computing</i>) says that every computing model is simulable by a Turing Machine with at most a polynomial overhead.<p> Quantum computing theory provides a model that seems to violate this assertion. Particularly, using a quantum computer (whatever it will be), it could be possible to efficiently solve classes of problems that are intractable nowadays using a classical computer, such as factorization.<p> How is this possible? Quantum computing relies on some strange properties of quantum mechanics, called <i>superpositions, entanglement, quantum parallelism</i>.<p> In order to take a brief look to these concepts, let's introduce quantum bits, a.k.a. <i>qubits</i>. They behave in part like classical bit, but they can also present "almost ghostly overlays of many different states", commonly known as superpositions of states. For example, it's possible for a qubit to be at the same time in its two states 1 and 2. Better, qubit is in a state where an observer has 1/2 probability to measure state 1 and 1/2 probability to measure state 0. With the notation commonly used in quantum theory:<p> <center>1/2(|0&gt; + |1&gt;)</center><p> Unfortunately, measuring the state of a quantum bit alters its state. So if we measure the state of the qubit considered, we could measure state |1&gt; or |0&gt; with the same probability 1/2, but after the measurement the qubit will be in state |1&gt; or |0&gt;, depending on our measurement.<p> You could say this is not so useful. Yes. And no. Juxtaposing many qubits we can obtain quantum registers. For example, using 8 qubits in the state 1/2(|0&gt; + |1&gt;) we obtain a register where <strong>every</strong> state (0..2<sup>8</sup>-1) can be measured, with the same probability. Every integer that can be expressed with 8 bits is "contained" (in the sense explained above) in this quantum register.<p> The interesting thing is that if we apply an operator to this register and we put the result in a second register, this register will contain <strong>every</strong> result that can be obtained applying the operator to the values that are contained in the first register.<p> As I said for qubits, the act of measuring alters the state of the registers. But if we measure the value of the second register, even the state of the first register will collapse to the correspondig value. This is called <i>entanglement</i>. So if we measure <i>f(x)</i> from the second register, we will measure <i>x</i> from the firsti one.<p> There's no quantum measurement possible to extract from the second register all the information about the function <i>f</i>. But note that the operator <b>performed an exponential quantity of operations in an unitary time</b>. This is called <i>quantum parallelism</i>. And, fortunately, there are other methods to obtain useful information about <i>f</i>. One of these methods (Discrete Fourier Transform, DFT) has been used by Shor to obtain a probabilistic quantum algorithm for factorization, that is known as an intractable problem in classical complexity theory. I think this is not the place to give other explanations: there's a lot of infos available on the net. I put some link at the end of this node. <h2>Quantum::Superpositions</h2> I've shown that Quantum Computing model permits to perform multiple operations in a single step by mean of superpositions. [cpan://Quantum::Superpositions] adds new linguistic tools to Perl (<code>any</code> and <code>all</code>) inspired to quantum mechanics.<p> They both produce Superpositions, i.e. scalars that can partecipate to any arithmetic or logic operations due to their nature, but with "parallel semantic": when a Superposition partecipate to an arithmetic operation, this operation if perfomed in parallel on every element of the Superposition; when the Superposition partecipate in a logical operation, its truth value is true or false depending on the truth value of its elements, in a disjuntive or conjuntive way, depending on the operator used to build the Superposition (respectively: <code>any</code> or <code>all</code>). I've said "parallel semantic" but internals of this module actually cycle trough every value of the Superposition to perform the operation.<p> So, one could write this program using [cpan://Quantum::Superpositions]: <code> \$product = any(1, 2, 3) * any( 2, 3, 4); print eigenvalues( \$product ); </code><p> <code>\$product</code> is a new Superposition that contain every possible result of the multiplication of the numbers (1, 2, 3) and the numbers (2, 3, 4) (<code>\$product</code> is <code>any(8,9,2,3,4,12,6)</code>). <code>eigenvalues</code> is a useful function that returns all the states that our Superposition represent (<i>In this context</i>. See the documentation for details).<p> Superpositions can also be passed to subroutines. The subroutine <strong>has not to know</strong> that what is going to be passed will be a superposition, but it will return a superposition of the results (as in the example of the operator applied to the quantum register).<p> Quantum::Superpositions also allows to express succinctly complex logical conditions. From the examples found in the documentation:<p> <code> \$ideal = any( all("tall", "rich", "handsome"), all("rich", "old"), all("smart","Australian","rich") ); while (@features = get_description) { if (any(@features) eq \$ideal) { print "True love"; } } </code><p> Here we build a disjunctive superposition of conjunctive superpositions (note the clarity with the concept of being the ideal is expressed). Then we cycle through a group of descriptions of (I guess :)) men, we build a superposition from the description (<code>any(@features)</code>) and we compare it disjunctively against our <code>\$ideal</code>. In this case, is like cycling and comparing against our set of ideals: i.e. <code>if (any(@features) eq all( "tall", "rich", "handsome"))</code>. We want that a subset of @features is equal to set ("tall", "rich", "handsome"). <h2>Using Quantum::Superpositions</h2> First of all, a word about performance.<br> [cpan://Quantum::Superpositions] has not to be intended as a practical way to do things in Perl. While it provides very succinct and smart idioms, their implementations are easily less efficient than a "hand-made" solution, because Quantum::Superpositions actually <strong>emulates</strong> a quantum computer. It isn't, of course, true quantum parallelism. So, this apparently very efficient factorization algorithm (from the examples of module documentation):<p> <table border="0"> <tr> <td width="60%"> <code> sub factors { my (\$n) = @_; my \$q = \$n / any(2..\$n-1); return eigenstates(floor(\$q)==\$q); } </code><p> ...will be comparable to this one from the point of view of efficiency:<p> <code> sub factors { my (\$n) = @_; my @q = map { \$n / \$_ } (2..\$n-1); return grep { floor( \$_ ) == \$_ } @q; } </code> </td> <td valign="top"> Beware!, the output differ, because in <code>floor(\$q)==\$q</code> we are asking for a numerical value of the superposition <code>\$q</code>, that is generated by this code <code>my @states = \$_->eigenstates; return \$states[rand @states]</code>. As I stated above, is in a state where we can measure with the same probability every value. Very funny, isn't it? :) </td> </tr> </table> <p> Also, [cpan://Quantum::Superpositions] provides some, let's say, extra-physics functions that have no counterpart in nature, such as the function <code>eigenstates</code> (remember, <i>"there's no quantum measurement possible to extract all the information..."</i>). So this module should be carefully used if you want to study quantum computing (but there are better tools).<p> [cpan://Quantum::Superpositions] is very useful to express, shortly, complex conditions that should be coded with <code>grep</code>/<code>map</code> combinations, as in the example of the ideal man. And it has great value, providing a good example of use of [cpan://Class::Multimethods]. <h2>References</h2> <ol> <li><i>"Quantum Theory, the Church-Turing principle and the universal quantum computer"</i>. This classical paper could be find on [http://www.qubit.org/people/david/David.html|David Deutsch's Home Page] <li>Adriano Barenco, <i>Quantum physics and computers</i>. Contemporary Physics, 1996, volume 37, number 5, pages 375-389. I don't know if this article is available on the net. <li>[http://www.imsa.edu/~matth/cs299/papertex.html|Quantum Computing and Shor's Algorithm] illustrates in detail Shor's factorization algorithm and contains a C++ implementation of the algorithm. Original paper is <i>Shor, P.W., 1994, Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, p.124</i>. <li><i>The Emperor's New Mind</i> by Roger Penrose. This book does not directly concern quantum computing, but provides a good introduction to foundations of computer science like Turing machines and recursive functions. It contains also a large section about quantum theory. <li>There's another module on CPAN inspired to Quantum theory: [cpan://Quantum::Entanglement] </ol> QM-like superpositions in Perl