> > Should I point out that RFC 225 (Superpositions) actually covers
> > most of this?
> >
> > C<null> is equivalent in semantics to C<any()> or C<all()>.
>
> I'd love to read your not yet available paper to which the RFC
> refers. However, until it is available, and I have time to read it,
> I'll spend my time reading proposals and discussions that are
> available.
I know we're all under a great deal of pressure as the deadlines draw
near, but let's *try* and preserve the positive tone that has pervaded
this discussions until now. Sniping -- even politely -- is only
counterproductive.
Meanwhile, please accept my apologies that other commitments have not
allowed me the time to finish the full paper on the topic.
I hope you won't mind my pointing out that the documentation of the
Quantum::Superpositions module -- to which the RFC also refers -- does
provide a comprehensive exposition of superpositions.
I take the liberty of reprinting it for you below.
Damian
-----------cut-----------cut-----------cut-----------cut-----------cut----------
NAME
Quantum::Superpositions - QM-like superpositions in Perl
SYNOPSIS
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") );
BACKGROUND
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).
DESCRIPTION
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.
Composite Superpositions
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".
Eigenstates
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);
Boolean evaluation of superpositions
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 comparsions 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.
String evaluation of superpositions
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*)"'.
Numerical evaluation of superpositions
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)];
Superpositions as subroutine arguments
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'];
EXAMPLES
Primality testing
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 membership and intersection
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
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);
}
Query processing
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 {
if (index($dbstr, $target) >= 0) {
return $dbstr;
}
}
$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;
