SYNOPSIS

use Quantum::Entanglement qw(:DEFAULT :complex :QFT);
my $c = entangle(1,0,i,1); # $c = |0> + i|1>
my $d = entangle(1,0,1,1); # $d = |0> + |1>
$e = $c * $d; # $e now |0*0> + i|0*1> + |1*0> + i|1*1>, connected to $c, $d
if ($e == 1) { # observe, probabilistically chose an outcome
# if we are here, ($c,$d) = i|(1,1)>
print "* \$e == 1\n";
}
else { # one of the not 1 versions of $e chosen
# if we are here, ($c,$d) = |(0,0)> + i|(1,0)> + |(0,1)>
print "* \$e != 1\n";
}

BACKGROUND

 "Quantum Mechanics - the dreams that stuff is made of."

Quantum mechanics is one of the stranger things to have emerged from science over the last hundred years. It has led the way to new understanding of a diverse range of fundamental physical phenomena and, should recent developments prove fruitful, could also lead to an entirely new mode of computation where previously intractable problems find themselves open to easy solution.

While the detailed results of quantum theory are hard to prove, and even harder to understand, there are a handful of concepts from the theory which are more easily understood. Hopefully this module will shed some light on a few of these and their consequences.

One of the more popular interpretations of quantum mechanics holds that instead of particles always being in a single, well defined, state they instead exist as an almost ghostly overlay of many different states (or values) at the same time. Of course, it is our experience that when we look at something, we only ever find it in one single state. This is explained by the many states of the particle collapsing to a single state and highlights the importance of observation.

In quantum mechanics, the state of a system can be described by a set of numbers which have a probability amplitude associated with them. This probability amplitude is similar to the normal idea of probability except for two differences. It can be a complex number, which leads to interference between states, and the probability with which we might observe a system in a particular state is given by the modulus squared of this amplitude.

Consider the simple system, often called a qubit, which can take the value of 0 or 1. If we prepare it in the following superposition of states (a fancy way of saying that we want it to have many possible values at once):

  particle = 1 * (being equal to 1) + (1-i) * (being equal to 0)

we can then measure (observe) the value of the particle. If we do this, we find that it will be equal to 1 with a probability of

  1**2 / (1**2 + (1-i)(1+i) )

and equal to zero with a probability of

 (1+i)(1-i) / (1**2 + (1-i)(1+i) )

the factors on the bottom of each equation being necessary so that the chance of the particle ending up in any state at all is equal to one.

Observing a particle in this way is said to collapse the wave-function, or superposition of values, into a single value, which it will retain from then onwards. A simpler way of writing the equation above is to say that

 particle = 1 |1> + (1-i) |0>

where the probability amplitude for a state is given as a 'multiplier' of the value of the state, which appears inside the "| >" pattern (this is called a ket, as sometimes the bra or "< |", pattern appears to the left of the probability amplitudes in these equations).

Much of the power of quantum computation comes from collapsing states and modifying the probability with which a state might collapse to a particular value as this can be done to each possible state at the same time, allowing for fantastic degrees of parallelism.

Things also get interesting when you have multiple particles together in the same system. It turns out that if two particles which exist in many states at once interact, then after doing so, they will be linked to one another so that when you measure the value of one you also affect the possible values that the other can take. This is called entanglement and is important in many quantum algorithms.

DESCRIPTION

Essentially, this allows you to put variables into a superposition of states, have them interact with each other (so that all states interact) and then observe them (testing to see if they satisfy some comparison operator, printing them) which will collapse the entire system so that it is consistent with your knowledge.

As in quantum physics, the outcome of an observation will be the result of selecting one of the states of the system at random. This might affect variables other than the ones observed, as they are able to remember their history.

For instance, you can say:

 $foo = entangle(1,0,1,1); # foo = |0> + |1>
 $bar = entangle(1,0,1,1); # bar = |0> + |1>

if at this point we look at the values of $foo or $bar, we will see them collapse to zero half of the time and one the other half of the time. We will also find that us looking at $foo will have no effect on the possible values, or chance of getting any one of those values, of $bar.

If we restrain ourselves a little and leave $foo and $bar unobserved we can instead play some games with them. We can use our entangled variables just as we would any other variable in perl, for instance,

 $c = $foo * $bar;

will cause $c to exist in a superposition of all the possible outcomes of multiplying each state of $foo with each state in $bar. If we now measure the value of $c, we will find that one quarter of the time it will be equal to one, and three quarters of the time it will be equal to zero.

Lets say we do this, and $c turns out to be equal to zero this time, what does that leave $foo and $bar as? Clearly we cannot have both $foo and $bar both equal to one, as then $c would have been equal to one, but all the other possible values of $foo and $bar can still occur. We say that the state of $foo is now entangled with the state of $bar so that

 ($foo, $bar ) = |0,0> + |0,1> + |1,0>.

If we now measure $foo, one third of the time it will be equal to one and two thirds of the time, it will come out as zero. If we do this and get one, this means that should we observe $bar it will be equal to zero so that our earlier measurement of $c still makes sense.

Use of this module

To use this module in your programs, simply add a

 use Quantum::Entanglement;

line to the top of your code, if you want to use complex probability amplitudes, you should instead say:

 use Quantum::Entanglement qw(:complex :DEFAULT);

which will import the "Math::Complex i Re Im rho theta arg cplx cplxe" functions / constants into your package.

You can also import a Quantum Fourier transform, which acts on the probability amplitudes of a state (see below) by adding a ":QFT" tag.

This module adds an "entangle" function to perl, this puts a variable into multiple states simultaneously. You can then cause this variable to interact with other entangled, or normal, values the result of which will also be in many states at once.

The different states which a variable can take each have an associated complex probability amplitude, this can lead to interesting behaviour, for instance, a root-not logic gate (see q_logic, below).

entangle

This sets up a new entangled variable:

 $foo = entangle(prob1, val1, prob2, val2, ...);

The probability values are strictly speaking probability amplitudes, and can be complex numbers (corresponding to a phase or wave-ish nature (this is stretching things slightly...)). To use straight numbers, just use them, to use complex values, supply a Math::Complex number.

Thus

 $foo = entangle(1,  0, 1+4*i, 1);

corresponds to:

 foo = 1|0> + (1 + 4i)|1>

The probabilities do not need to be normalized, this is done by the module whenever required (ie. when observing variables).

Non-observational operations

We can now use our entangled variable just as we would any normal variable in perl. Much of the time we will be making it do things where we do not find anything out about the value of our variable, if this is the case, then the variable does not collapse, although any result of its interactions will be entangled with itself.

Observational Operators

Whenever you perform an operation on an entangled variable which should increase your level of knowledge about the value of the variable you will cause it to collapse into a single state or set of states. All logical comparison ("==", "gt" ....) operators, as well as string and num -ifying and boolean observation will cause collapse.

When an entangled variable is observed in this way, sets of states which would satisfy the operator are produced (ie. for $a < 2, all states <2 and all >= 2). One of these sets of states is then selected randomly, using the probability amplitudes associated with the states. The result of operating on this state is then returned. Any other states are then destroyed.

For instance, if

 $foo = entangle(1,2,1,3,1,5,1,7);
        # |2> +|3> + |5> +|7>
then saying
 print '$foo is greater than four' if ($foo > 4);

will cause $foo to be either "|2> + |3>" or "|5> +7>".

Of course, if you had said instead:

  $foo = entangle(-1,2,1,3,1,5,1,7);
           # -1|2> + |3> + |5> +|7>

then if $foo was measured here, it would come out as any one of 2,3,5,7 with equal likelyhood (remember, amplitude squared). But saying

 print '$foo is greater than four' if ($foo > 4);

will cause foo to be "|2> or 3>" with a probability of "(-1 + 1) == 0" or "|5 or 7>" with probability of "(1 + 1)/2 == 1". Thus "$foo > 4" will always be true.

It is possible to perform operations like these on an entangled variable without causing collapse by using "p_op" (below).

When performing an observation, the module can do two things to the states which can no longer be valid (those to which it did not collapse, |2 or 3> in the example above). It can either internally set the probability of them collapsing to be zero or it can delete them entirely. This could have consequences if you are writing parallel functions that rely on there being a certain number of states in a variable, even after collapse.

The default is for collapsed states to be destroyed, to alter this behaviour, set the $Quantum::Entanglement::destroy variable to a false value. In general though, you can leave this alone.

Dammit Jim, I can't change the laws of physics

Although not the default, it is possible to cause observation (for boolean context or with comparison operators only) to act in a more purposeful manner. If the variable:

 $Quantum::Entanglement::conform

has a true value, then the overloaded operations provided by this module will try their very best to return ``truth'' instead of selecting randomly from both ``true'' and ``false'' outcomes.

For example:

 $foo = entangle(1,0,1,1,1,3); # foo = |0> + |1> + |3>
 $Quantum::Entanglement::conform = 1;
 print "\$foo > 0\n" if $foo > 0;
                               # foo now = |1> + |3>
 print "\$foo == 3\n" if $foo == 3;
                               # foo now = |3>

will always output:

 $foo > 0
 $foo == 3

Of course, setting this variable somewhat defeats the point of the module, but it could lead to some interesting pre-calculating algorithms which are fed with entangled input, which is then later defined (by testing ==, say )with the answer of the calculation appearing, as if by magic, in some other variable. See also the section save_state.

p_op

This lets you perform conditional operations on variables in a superposition of states without actually looking at them. This returns a new superposed variable, with states given by the outcome of the p_op. You cannot, of course, gain any information about the variables involved in the p_op by doing this.

 $rt = p_op(var1, op, var2, code if true, code if false).

"op" should be a string representing the operation to be performed (eg. "=="). The two code arguments should be references to subs the return values of which will be used as the value of the corresponding state should the expression be true or false.

If no code is provided, the return value of the operator itself is evaluated in boolean context, if true, 1 or if false, 0 is used as the corresponding state of the returned variable. Only one of var1 and var2 need to be entangled states. The values of the states being tested are placed into the $QE::arg1 and $QE::arg2 variables should the subroutines want to play with them (these are localized aliases to the actual values, so modify at your peril (or pleasure)).

The semantics are best shown by example:

 $gas = entangle(1, 'bottled', 1, 'released');
   # gas now in states |bottled> + |released>
 $cat_health = p_op($gas, 'eq', 'released',
                         sub {'Dead'},
                         sub {'Alive'});
   # cat,gas now in states |Alive, bottled> + |Dead, released>

This is similar to parallel execution of the following psuedo code:

 if (gas is in bottle) { # not probabilistic, as we don't look
   cat is still alive
 }
 else {
   cat is dead
 }

The cat can now be observed (with a conditional test say) and doing so will collapse both the cat and the gas:

 if ($cat_health eq 'Dead') {# again, outcome is probabilistic
   # thus gas = |released>
 }
 else {
   # thus gas = |bottled>
 }

This also lets you use some other 'binary' operators on a superposition of states by immediatly observing the return value of the parallel op.

 $string = entangle(1,'aa', 1, 'bb', 1, 'ab', 1, 'ba');
 $regex = qr/(.)\1/;
 if (q_op($string, '=~', $regex)) { # again, probabilistic
   # if here, string = |aa> + |bb>
 }
 else {
   # if here, string = |ab> + |ba>
 }

p_func

This lets you perform core functions and subs through the states of a superposition without observing and produce a new variable corresponding to a superposition of the results of the function.

 p_func("func" ,entangled var,[more vars,] [optional args])

Any number of entangled variables can be passed to the function, optional args begin with the first non-entangled var.

The optional args will be passed to the subroutine or function unmodified.

eg. "p_func('substr', $foo, 1,1)" will perform "substr($state, 1,1)" on each state in $foo. Saying "p_func('substr', $foo,$bar,1)" will evaluate "substr($s_foo, $s_bar,1)" for each state in $foo and $bar.

You can also specify a subroutine, either in the same package that "p_func" is called from, or with a fully qualified name.

 sub foo {my $state = $_[0]; return ${$_[1]}[$state]}
 @foo = qw(one two three);
 $foo = entangle(1,1,1,2,1,3); # |1> + |2> + |3>
 $bar = p_func('foo', $foo, \@foo);
 # bar now |one> + |two> + |three>

You can also pass a code reference as first arg (cleaner)...

 $bar = p_func(\&foo, $foo, \@foo);

q_logic

This allows you to create new states, increasing the amount of global state as you do so. This lets you apply weird quantum logic gates to your variables, amongst other things.

 q_logic(code ref, entangled var [,more vars] );

The code ref is passed a list of probabilities and values corresponding to the state currently being examined. (prob, val, [prob, val..]) code ref must return a list of the following format:

 (prob, val, prob, val ...) # as entangle basically

For instance, this is a root-not gate:

 sub root_not {
   my ($prob, $val) = @_;
   return( $prob * (i* (1/sqrt(2))), $val,
           $prob * (1/sqrt(2)), !$val ? 1 : 0);
 }
 $foo = entangle(1,0);
 $foo = q_logic(\&root_not, $foo);
 # if $foo is observed here, it will collapse to both 0 and 1, at random
 $foo = q_logic(\&root_not, $foo);
 print "\$foo is 1\n" if $foo; # always works, $foo is now 1.

This corresponds to the following:

 foo = |0>
 root_not( foo )
 foo is now in state: sqrt(2)i |0> + sqrt(2) |1>
 root_not (foo)
 foo in state: (0.5 - 0.5) |0> + (0.5i + 0.5i) |1>
 which if observed gives
 foo = 0|0> + i|1> which must collapse to 1.

Neat, huh?

save_state

Having set up a load of entangled variables, you might wish to store their superposed state for later restoration. This is acheived using the "save_state" function:

 $state = save_state( [list of entangled variables] );

To restore the states of the entangled variables, simply call the "restore_state" method on the $state:

  ($foo, $bar) = $state->restore_state;

The variables return by "restore_state" will no longer be entangled to anything they were previously connected to. If multiple variables have their state saved at once, then any connections between them will remain.

See the demo calc_cache for an example of use.

QFT

This provides a quantum fourier transform which acts on the probability amplitudes of a state, creating a new state with the same values as the initial state but with new probability amplitudes. FTs like this are used in many quantum algorithms where it is important to find the periodicity of some function (for instance, Shor).

This will only work if you have carefully populated your states, essentially if all seperately "entangle"d variables do not interact. This sort of breaks encapsulation, so might change in the future!

See "~/demo/shor.pl" for an example of the use of this function.

Quantum::Entanglement::show_states

This allows you to find out the states that your variables are in, it does not count as observation.

If called as a method it will only return the states available to that variable, thus:

 $foo = entangle(1,0,1,1);
 print $foo->show_states;

outputs:

 1|0>   1|1>

If a variable is entangled with other superposed values, then calling "save_state" with an additional true argument will display the states of all the variables which have interacted together.

 print $foo->show_states(1);

If two variables have not yet interacted, then they will not appear in the state space of the other.

The ordering of the output of this function may change in later versions of this module.

Entangling subroutines

It is possible to entangle a set of subroutine references and later call them in parallel with the same set of arguments. The subroutines will always be called in scalar context. The return values of the subroutines will be present in the entangled variable returned.

eg.

 $subs = entangle(1 => sub {return $_[0}, 1=>sub {return $_[1]});
 $return = $subs->(qw(chalk cheese));
  # $return now |chalk> + |cheese>

EXPORT

This module exports quite a bit, "entangle", "save_state", "p_op", "p_func" and "q_logic". If used with qw(:complex) it will also export the following functions / constants from the Math::Complex module: "i Re Im rho theta arg cplx cplxe".

AUTHOR

Alex Gough ([email protected]). Any comments, suggestions or bug reports are warmly welcomed.

Shortcomings

This module does fall short of physical reality in a few important areas, some of which are listed below:

No eigenfunction like behaviour

All operators share the same set of eigenfunctions, in real QM this is sometimes not the case, so observing one thing would cause some other thing (even if already observed) to fall into a superposition of states again.

Certain observables cannot simultaneously have precisely defined values.

This follows from the point above. The famous uncertainty principle follows from the fact that position and momentum have different sets of eigenfunctions. In this module, it is always possible to collapse the system so that a value is known for every entangled variable.

Perl is not a quantum computing device

Perl, alas, is currently only implemented on classical computers, this has the disadvantage that any quantum algorithm will not run in constant time but will quite likely run in exponential time. This might be remedied in future releases of perl. Just not anytime soon.

Quantum information cannot be copied with perfect fidelity

It is impossible to perfectly clone a real entangled state without 'damaging' in some way either the original or the copy. In this module, it is possible for this to happen as we have special access to the states of our variables.

Cannot generate perfectly random numbers

It is well known that classical computers cannot produce a perfectly random sequence of numbers, as this module runs on one of these, it also suffers the same fate. It is possible to give a classical computer access to a perfect random number generator though (essentially by linking it to a suitable physical system) in which case this is no longer a problem.

COPYRIGHT

This code is copyright (c) Alex Gough, 2001,2002. All Rights Reserved. This module is free software. It may be used, redistributed and/or modified under the same terms as Perl itself.