modulereview
larsen
<table border="0">
<tr>
<td width="50%"> </td>
<td width="50%"><blockquote>
<[larsen]> I think I'll add a disclaimer...<br>
<[larsen]> <i>"No cat has been hurt to write this review"</i><br>
<[neshura]> lol<br>
<[neshura]> IMPOSSIBLE<br>
<p>
<[larsen]> hi neshura, I didn't noticed you<br>
<[larsen]> :)<br>
<[neshura]> 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> + |1>)</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> or |0> with the same probability 1/2,
but after the measurement the qubit will be in state |1> or |0>,
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> + |1>) 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 = $_[0]->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