Provided by: libquantum-superpositions-perl_2.03-1_all bug


       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

       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

       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

               $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),
               @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"),

       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

               print "The factor was: ",

               print "Don't use any of:",

   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

       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

       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

   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: ",

       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...",

   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

       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'];


   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.

               @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),

       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
                               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 (

       Now maintainted by Steven Lembark (


       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