Quantum::Superpositions - QM-like superpositions in Perl
This document describes version 1.03 of Quantum::Superpositions, released August
11, 2000.
use Quantum::Superpositions;
if ($x == any($a, $b, $c)) { ... }
while ($nextval < all(@thresholds)) { ... }
$max = any(@value) < all(@values);
use Quantum::Superpositions BINARY => [ CORE::index ];
print index( any("opts","tops","spot"), "o" );
print index( "stop", any("p","s") );
Under the standard interpretation of quantum mechanics, until they are observed,
particles exist only as a discontinuous probability function. Under the
Cophenhagen Interpretation, this situation is often visualized by imagining
the state of an unobserved particle to be a ghostly overlay of all its
possible observable states simultaneously. For example, a particle that might
be observed in state A, B, or C may be considered to be in a pseudo-state
where it is simultaneously in states A, B, and C. Such a particle is said to
be in a superposition of states.
Research into applying particle superposition in construction of computer
hardware is already well advanced. The aim of such research is to develop
reliable quantum memories, in which an individual bit is stored as some
measurable property of a quantised particle (a qubit). Because the particle
can be physically coerced into a superposition of states, it can store bits
that are simultaneously 1 and 0.
Specific processes based on the interactions of one or more qubits (such as
interference, entanglement, or additional superposition) are then be used to
construct quantum logic gates. Such gates can in turn be employed to perform
logical operations on qubits, allowing logical and mathematical operations to
be executed in parallel.
Unfortunately, the math required to design and use quantum algorithms on quantum
computers is painfully hard. The Quantum::Superpositions module offers another
approach, based on the superposition of entire scalar values (rather than
individual qubits).
The Quantum::Superpositions module adds two new operators to Perl:
"any" and "all".
Each of these operators takes a list of values (states) and superimposes them
into a single scalar value (a superposition), which can then be stored in a
standard scalar variable.
The "any" and "all" operators produce two distinct kinds of
superposition. The "any" operator produces a disjunctive
superposition, which may (notionally) be in any one of its states at any time,
according to the needs of the algorithm that uses it.
In contrast, the "all" operator creates a conjunctive superposition,
which is always in every one of its states simultaneously.
Superpositions are scalar values and hence can participate in arithmetic and
logical operations just like any other type of scalar. However, when an
operation is applied to a superposition, it is applied (notionally) in
parallel to each of the states in that superposition.
For example, if a superposition of states 1, 2, and 3 is multiplied by 2:
$result = any(1,2,3) * 2;
the result is a superposition of states 2, 4, and 6. If that result is then
compared with the value 4:
if ($result == 4) { print "fore!" }
then the comparison also returns a superposition: one that is both true and
false (since the equality is true for one of the states of $result and false
for the other two).
Of course, a value that is both true and false is of no use in an "if"
statement, so some mechanism is needed to decide which superimposed boolean
state should take precedence.
This mechanism is provided by the two types of superposition available. A
disjunctive superposition is true if any of its states is true, whereas a
conjunctive superposition is true only if all of its states are true.
Thus the previous example does print "fore!", since the "if"
condition is equivalent to:
if (any(2,4,6) == 4)...
It suffices that any one of 2, 4, or 6 is equal to 4, so the condition is true
and the "if" block executes.
On the other hand, had the control statement been:
if (all(2,4,6) == 4)...
the condition would fail, since it is not true that all of 2, 4, and 6 are equal
to 4.
Operations are also possible between two superpositions:
if (all(1,2,3)*any(5,6) < 21)
{ print "no alcohol"; }
if (all(1,2,3)*any(5,6) < 18)
{ print "no entry"; }
if (any(1,2,3)*all(5,6) < 18)
{ print "under-age" }
In this example, the string "no alcohol" is printed because the
superposition produced by the multiplication is the Cartesian product of the
respective states of the two operands: "all(5,6,10,12,15,18)". Since
all of these resultant states are less that 21, the condition is true. In
contrast, the string "no entry" is not printed, because not all the
product's states are less than 18.
Note that the type of the first operand determines the type of the result of an
operation. Hence the third string -- "underage" -- is printed,
because multiplying a disjunctive superposition by a conjunctive superposition
produces a result that is disjunctive: "any(5,6,10,12,15,18)". The
condition of the "if" statement asks whether any of these values is
less than 18, which is true.
The states of a superposition may be any kind of scalar value -- a number, a
string, or a reference:
$wanted = any("Mr","Ms").any(@names);
if ($name eq $wanted) { print "Reward!"; }
$okay = all(\&check1,\&check2);
die unless $okay->();
my $large =
all( BigNum->new($centillion),
BigNum->new($googol),
BigNum->new($SkewesNum)
);
@huge = grep {$_ > $large} @nums;
More interestingly, since the individual states of a superposition are scalar
values and a superposition is itself a scalar value, a superposition may have
states that are themselves superpositions:
$ideal = any( all("tall", "rich", "handsome"),
all("rich", "old"),
all("smart","Australian","rich")
);
Operations involving such a composite superposition operate recursively and in
parallel on each its states individually and then recompose the result. For
example:
while (@features = get_description)
{
if (any(@features) eq $ideal)
{
print "True love";
}
}
The "any(@features) eq $ideal" equality is true if the input
characteristics collectively match any of the three superimposed conjunctive
superpositions. That is, if the characteristics collectively equate to each of
"tall" and "rich" and "handsome", or to both
"rich" and "old", or to all three of "smart" and
"Australian" and "rich".
It is useful to be able to determine the list of states that a given
superposition represents. In fact, it is not the
states per se, but the
values to which the states may collapse -- the
eigenstates that are
useful.
In programming terms this is the set of values @ev for a given superposition $s
such that "any(@ev) == $s" or "any(@ev) eq $s".
This list is provided by the "eigenstates" operator, which may be
called on any superposition:
print "The factor was: ",
eigenstates($factor);
print "Don't use any of:",
eigenstates($badpasswds);
The examples shown above assume the same meta-semantics for both arithmetic and
boolean operations, namely that a binary operator is applied to the Cartesian
product of the states of its two operands, regardless of whether the operation
is arithmetic or logical. Thus the comparison of two superpositions produces a
superposition of 1's and 0's, representing any (or all) possible comparisons
between the individual states of the two operands.
The drawback of applying arithmetic metasemantics to logical operations is that
it causes useful information to be lost. Specifically, which states were
responsible for the success of the comparison. For example, it is possible to
determine if any number in the array @newnums is less than all those in the
array @oldnums with:
if (any(@newnums) < @all(oldnums))
{
print "New minimum detected";
}
But this is almost certainly unsatisfactory, because it does not reveal which
element(s) of @newnum caused the condition to be true.
It is, however, possible to define a different meta-semantics for logical
operations between superpositions; one that preserves the intuitive logic of
comparisons but also gives limited access to the states that cause those
comparisons to succeed.
The key is to deviate from the arithmetic view of superpositional comparison
(namely, that a compared superposition yields a superposition of compared
state combinations). Instead, the various comparison operators are redefined
so that they form a superposition of those eigenstates of the left operand
that cause the operation to be true. In other words, the old meta-semantics
superimposed the result of each parallel comparison, whilst the new
meta-semantics superimposes the left operands of each parallel comparison that
succeeds.
For example, under the original semantics, the comparisons:
all(7,8,9) <= any(5,6,7) #A
all(5,6,7) <= any(7,8,9) #B
any(6,7,8) <= all(7,8,9) #C
would yield:
all(0,0,1,0,0,0,0,0,0) #A (false)
all(1,1,1,1,1,1,1,1,1) #B (true)
any(1,1,1,1,1,1,0,1,1) #C (true)
Under the new semantics they would yield:
all(7) #A (false)
all(5,6,7) #B (true)
any(6,7) #C (true)
The success of the comparison (the truth of the result) is no longer determined
by the
values of the resulting states, but by the
number of
states in the resulting superposition.
The Quantum::Superpositions module treats logical operations and boolean
conversions in exactly this way. Under these meta-semantics, it is possible to
check a comparison and also determine which eigenstates of the left operand
were responsible for its success:
$newmins = any(@newnums) < all(@oldnums);
if ($newmins)
{
print "New minima found:", eigenstates($newmins);
}
Thus, these semantics provide a mechanism to conduct parallel searches for
minima and maxima :
sub min { eigenstates( any(@_) <= all(@_) ) }
sub max { eigenstates( any(@_) >= all(@_) ) }
These definitions are also quite intuitive, almost declarative: the minimum is
any value that is less-than-or-equal-to all of the other values; the maximum
is any value that is greater-than-or-equal to all of them.
Converting a superposition to a string produces a string that encode the
simplest set of eigenstates equivalent to the original superposition.
If there is only one eigenstate, the stringification of that state is the string
representation. This eliminates the need to explicitly apply the
"eigenstates" operator when only a single resultant state is
possible. For example:
print "lexicographically first: ",
any(@words) le all(@words);
In all other cases, superpositions are stringified in the format: "all(
eigenstates)" or "any(
eigenstates)".
Providing an implicit conversion to numeric (for situations where superpositions
are used as operands to an arithmetic operation, or as array indices) is more
challenging than stringification, since there is no mechanism to capture the
entire state of a superposition in a single non-superimposed number.
Again, if the superposition has a single eigenstate, the conversion is just the
standard conversion for that value. For instance, to output the value in an
array element with the smallest index in the set of indices @i:
print "The smallest element is: ",
$array[any(@i)<=all(@i)];
If the superposition has no eigenstates, there is no numerical value to which it
could collapse, so the result is "undef".
If a disjunctive superposition has more than one eigenstate, that superposition
could collapse to any of those values. And it is convenient to allow it to do
exactly that -- collapse (pseudo-)randomly to one of its eigenstates. Indeed,
doing so provides a useful notation for random selection from a list:
print "And the winner is...",
$entrant[any(0..$#entrant)];
When a superposition is used as a subroutine argument, that subroutine is
applied in parallel to each state of the superposition and the results
re-superimposed to form the same type of superposition. For example, given:
$n1 = any(1,4,9);
$r1 = sqrt($n1);
$n2 = all(1,4,9);
$r2 = pow($n2,3);
$r3 = pow($n1,$r1);
then $r1 contains the disjunctive superposition "any(1,2,3)", $r2
contains the conjunctive superposition "all(1,64,729)", and <$r3
> contains the conjunctive superposition
"any(1,4,9,16,64,81,729)".
Because the built-in "sqrt" and "pow" functions don't know
about superpositions, the module provides a mechanism for informing them that
their arguments may be superimposed.
If the call to "use Quantum::Superpositions" is given an argument
list, that list specifies which functions should be rewritten to handle
superpositions. Unary functions and subroutine can be "quantized"
like so:
sub incr { $_[0]+1 }
sub numeric { $_[0]+0 eq $_[0] }
use Quantum::Superpositions
UNARY => ["CORE::int", "main::incr"],
UNARY_LOGICAL => ["main::numeric"];
For binary functions and subroutines use:
sub max { $_[0] < $_[1] ? $_[1] : $_[0] }
sub same { my $failed; $IG{__WARN__}=sub{$failed=1};
return $_[0] eq $_[1] || $_[0]==$_[1] && !$failed;
}
use Quantum::Superpositions
BINARY => ['main::max', 'CORE::index'],
BINARY_LOGICAL => ['main::same'];
The power of programming with scalar superpositions is perhaps best seen by
returning the quantum computing's favourite adversary: prime numbers. Here,
for example is an O(1) prime-number tester, based on naive trial division:
sub is_prime
{
my ($n) = @_;
return $n % all(2..sqrt($n)+1) != 0
}
The subroutine takes a single argument ($n) and computes (in parallel) its
modulus with respect to every integer between 2 and "sqrt($n)". This
produces a conjunctive superposition of moduli, which is then compared with
zero. That comparison will only be true if all the moduli are not zero, which
is precisely the requirement for an integer to be prime.
Because "is_prime" takes a single scalar argument, it can also be
passed a superposition. For example, here is a constant-time filter for
detecting whether a number is part of a pair of twin primes:
sub has_twin
{
my ($n) = @_;
return is_prime($n) && is_prime($n+any(+2,-2);
}
Set operations are particularly easy to perform using superimposable scalars.
For example, given an array of values @elems, representing the elements of a
set, the value $v is an element of that set if:
$v == any(@elems)
Note that this is equivalent to the definition of an eigenstate. That
equivalence can be used to compute set intersections. Given two disjunctive
superpositions, "$s1=any(@elems1)" and "$s2=any(@elems2)",
representing two sets, the values that constitute the intersection of those
sets must be eigenstates of both <$s1> and $s2. Hence:
@intersection = eigenstates(all($s1, $s2));
This result can be extended to extract the common elements from an arbitrary
number of arrays in parallel:
@common = eigenstates( all( any(@list1),
any(@list2),
any(@list3),
any(@list4),
)
);
Factoring numbers is also trivial using superpositions. The factors of an
integer N are all the quotients q of N/n (for all positive integers n < N)
that are also integral. A positive number q is integral if floor(q)==q. Hence
the factors of a given number are computed by:
sub factors
{
my ($n) = @_;
my $q = $n / any(2..$n-1);
return eigenstates(floor($q)==$q);
}
Superpositions can also be used to perform text searches. For example, to
determine whether a given string ($target) appears in a collection of strings
(@db):
use Quantum::Superpositions BINARY => ["CORE::index"];
$found = index(any(@db), $target) >= 0;
To determine which of the database strings contain the target:
sub contains_str
{
return $dbstr if (index($dbstr, $target) >= 0;
}
$found = contains_str(any(@db), $target);
@matches = eigenstates $found;
It is also possible to superimpose the target string, rather than the database,
so as to search a single string for any of a set of targets:
sub contains_targ
{
if (index($dbstr, $target) >= 0)
{
return $target;
}
}
$found = contains_targ($string, any(@targets));
@matches = eigenstates $found;
or in every target simultaneously:
$found = contains_targ($string, all(@targets));
@matches = eigenstates $found;
Damian Conway (damian@conway.org)
Now maintainted by Steven Lembark (lembark@wrkhors.com)
There are undoubtedly serious bugs lurking somewhere in code this funky :-) Bug
reports and other feedback are most welcome.
Copyright (c) 1998-2002, Damian Conway. Copyright (c) 2002, Steven Lembark
All Rights Reserved.
This module is free software. It may be used, redistributed and/or modified
under the stame terms as Perl-5.6.1 (or later) (see
http://www.perl.com/perl/misc/Artistic.html).