|No such thing as a small change|
Quantum::Superpositionsby larsen (Parson)
|on Jul 22, 2001 at 15:35 UTC||Need Help??|
Item Description: QM-like superpositions in Perl
Quantum computing in a nutshellOne 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:
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::SuperpositionsI'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 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:
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::SuperpositionsFirst 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):
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.