This is PerlMonks "Mobile"

Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Item Description: QM-like superpositions in Perl

Review Synopsis:

 
<larsen> I think I'll add a disclaimer...
<larsen> "No cat has been hurt to write this review"
<neshura> lol
<neshura> IMPOSSIBLE

<larsen> hi neshura, I didn't noticed you
<larsen> :)
<neshura> now that you have noticed, bet you can't tell what my velocity is

-- Two monks on IRC :)

Quantum computing in a nutshell

One of the possible formulations of Church-Turing's thesis (actually it's not equivalent: is a reinforcement also known as thesis of sequential computing) says that every computing model is simulable by a Turing Machine with at most a polynomial overhead.

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.

How is this possible? Quantum computing relies on some strange properties of quantum mechanics, called superpositions, entanglement, quantum parallelism.

In order to take a brief look to these concepts, let's introduce quantum bits, a.k.a. qubits. 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:

1/2(|0> + |1>)

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.

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 every state (0..28-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.

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 every result that can be obtained applying the operator to the values that are contained in the first register.

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 entanglement. So if we measure f(x) from the second register, we will measure x from the firsti one.

There's no quantum measurement possible to extract from the second register all the information about the function f. But note that the operator performed an exponential quantity of operations in an unitary time. This is called quantum parallelism. And, fortunately, there are other methods to obtain useful information about f. 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.

Quantum::Superpositions

I've shown that Quantum Computing model permits to perform multiple operations in a single step by mean of superpositions. Quantum::Superpositions adds new linguistic tools to Perl (any and all) inspired to quantum mechanics.

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: any or all). I've said "parallel semantic" but internals of this module actually cycle trough every value of the Superposition to perform the operation.

So, one could write this program using Quantum::Superpositions:

$product = any(1, 2, 3) * any( 2, 3, 4); print eigenvalues( $product );

$product is a new Superposition that contain every possible result of the multiplication of the numbers (1, 2, 3) and the numbers (2, 3, 4) ($product is any(8,9,2,3,4,12,6)). eigenvalues is a useful function that returns all the states that our Superposition represent (In this context. See the documentation for details).

Superpositions can also be passed to subroutines. The subroutine has not to know 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).

Quantum::Superpositions also allows to express succinctly complex logical conditions. From the examples found in the documentation:

$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"; } }

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 (any(@features)) and we compare it disjunctively against our $ideal. In this case, is like cycling and comparing against our set of ideals: i.e. if (any(@features) eq all( "tall", "rich", "handsome")). We want that a subset of @features is equal to set ("tall", "rich", "handsome").

Using Quantum::Superpositions

First of all, a word about performance.
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 emulates a quantum computer. It isn't, of course, true quantum parallelism. So, this apparently very efficient factorization algorithm (from the examples of module documentation):

sub factors { my ($n) = @_; my $q = $n / any(2..$n-1); return eigenstates(floor($q)==$q); }

...will be comparable to this one from the point of view of efficiency:

sub factors { my ($n) = @_; my @q = map { $n / $_ } (2..$n-1); return grep { floor( $_ ) == $_ } @q; }
Beware!, the output differ, because in floor($q)==$q we are asking for a numerical value of the superposition $q, that is generated by this code my @states = $_[0]->eigenstates; return $states[rand @states]. As I stated above, is in a state where we can measure with the same probability every value. Very funny, isn't it? :)

Also, Quantum::Superpositions provides some, let's say, extra-physics functions that have no counterpart in nature, such as the function eigenstates (remember, "there's no quantum measurement possible to extract all the information..."). So this module should be carefully used if you want to study quantum computing (but there are better tools).

Quantum::Superpositions is very useful to express, shortly, complex conditions that should be coded with grep/map combinations, as in the example of the ideal man. And it has great value, providing a good example of use of Class::Multimethods.

References

  1. "Quantum Theory, the Church-Turing principle and the universal quantum computer". This classical paper could be find on David Deutsch's Home Page
  2. Adriano Barenco, Quantum physics and computers. Contemporary Physics, 1996, volume 37, number 5, pages 375-389. I don't know if this article is available on the net.
  3. Quantum Computing and Shor's Algorithm illustrates in detail Shor's factorization algorithm and contains a C++ implementation of the algorithm. Original paper is Shor, P.W., 1994, Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, p.124.
  4. The Emperor's New Mind 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.
  5. There's another module on CPAN inspired to Quantum theory: Quantum::Entanglement

Replies are listed 'Best First'.
Re: Quantum::Superpositions
by John M. Dlugosz (Monsignor) on Jul 23, 2001 at 08:50 UTC
    I had the chance to listen to Roger Penrose speak, and we asked him about Emporer's new Mind and other related topics. He didn't seem to feel that a quantum-computer violated the basic rules of computing--he said it's even been figured with an "oricle machine" and it still doesn't change what can and can't "be computed".

    So, I suppose a q-computer can factor numbers a lot faster, but it wasn't "impossible" before.