Quipper.Algorithms.CL.Auxiliary

This module defines general-purpose functions not specific to the Class Number algorithm, but required by it.

Classical functions

Control

assert :: Bool -> String -> a -> a

Assert that a condition is true, otherwise throwing an error with a given error message, in a functional setting.

assertM :: Monad m => Bool -> String -> m ()

Assert a condition, imperatively in a monad.

sequence_until :: Monad m => (a -> Bool) -> [m a] -> m (Maybe a)

Given a list of monadic actions and a predicate on their results, do the actions in sequence until one produces a result satisfying the predicate; return this result.

all_eq :: Eq a => [a] -> Bool

Test whether elements of a list are all equal

while :: (a -> Bool) -> (a -> a) -> a -> a

Apply a function to data while condition holds true. For example:

while (not . isReduced . fst) rho ideal

will apply the function rho to an ideal-with-distance while it is not yet reduced (until it is reduced).

bounded_while :: Integral int => (a -> Bool) -> int -> (a -> a) -> a -> a

Like while, but with a known bound on number of iterations. This construct can be converted to a quantum circuit, while a general unbounded while cannot be lifted.

bounded_iterate :: Integral int => int -> (a -> a) -> a -> [a]

A bounded version of Haskell iterate function that produces an infinite list. This function produces a finite bounded list.

Mathematical functions

primes :: Integral a => [a]

Generate primes using the Sieve of Eratosthenes. Straightforward implementation - when a prime is found, filter all of its multiples out of the already filtered list. This implementation may eventually blow out of stack, but it should grow with the number of primes, which seems to be O(log log n).

primes_to :: Integral a => a -> [a]

Generate primes up to a given number. See implementation of primes for details.

is_square_free :: Integral a => a -> Bool

Check if a number is square-free (by brute force).

jacobi_symbol :: (Integral a, Num b) => a -> a -> b

Compute the Jacobi symbol. The definition and algorithm description is taken from http://en.wikipedia.org/wiki/Jacobi_symbol.

mod_with_max :: Integral a => a -> a -> a -> a

mod_with_max x y max: reduce x modulo y, returning the unique representative x' in the range max – y < x' ≤ max.

divchk :: (Show a, Integral a) => a -> a -> a

Integer division with asserts making sure that the denominator indeed divides the numerator.

extended_euclid :: Integral a => a -> a -> (a, a, a)

extended_euclid a b: return (d,x,y), such that d = gcd(a,b), and ax + by = d.

divides :: Integral a => a -> a -> Bool

a divides b: return True if a divides b.

is_int :: (RealFrac a, Eq a) => a -> Bool

Test whether a real number is an integer.

continued_list :: Integral int => int -> int -> [int]

Generate the list of integers describing the continued fraction of a given rational number. Since the number is rational, the expansion is finite.

Each rational number q is equal to a unique expression of the form

where n ≥ 0, a₀ is an integer, a₁, …, a_n are positive integers, and a_n ≠ 1 unless n=0. This is called the (short) continued fraction expansion of q. The function continued_list inputs two integers num and denom, computes the continued fraction expansion of q = num / denom, and returns the non-empty sequence [a₀, …, a_n].

convergents :: (Integral int, Fractional a) => [int] -> [a]

Generate a list of convergents from a continued fraction (as described by the non-empty list of integers of that fraction).

Quantum functions

Generic blackboxing

blackbox :: (QData qa, QData qb) => String -> qb -> qa -> Circ (qa, qb)

Unimplemented components need to be given as black boxes — like named gates, except their types may not just be an endomorphism; like subroutines, except with only a placeholder on the inside.

For this module, black boxes are only needed for classical functional routines, i.e. with type qa -> Circ (qa, qb)

Boxed imported arithmetic

To reduce the printed sizes of circuits, we box all imported arithmetic components.

arithbox :: (QCData qa, QCData qb, QCurry qa_qb qa qb) => String -> qa_qb -> qa_qb

Like box, but prepends "Arith." to subroutine names, as a crude form of namespace management.

q_ext_euclid :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt, QDInt, QDInt)

Boxed analogue of q_ext_euclid.

q_add :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt)

Boxed analogue of q_add.

q_mult :: (QCData qa, QNum qa) => qa -> qa -> Circ (qa, qa, qa)

Boxed analogue of q_mult.

q_div_exact :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt)

Boxed analogue of q_div_exact.

q_add_in_place :: QDInt -> QDInt -> Circ (QDInt, QDInt)

Boxed analogue of q_add_in_place.

q_add_param_in_place :: IntM -> QDInt -> Circ QDInt

Boxed analogue of q_add_param_in_place.

q_div :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt)

Boxed analogue of q_div.

q_mult_param :: IntM -> QDInt -> Circ (QDInt, QDInt)

Boxed analogue of q_mult_param.

q_mod_unsigned :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt)

Boxed analogue of q_mod_unsigned.

q_sub_in_place :: QDInt -> QDInt -> Circ (QDInt, QDInt)

Boxed analogue of q_sub_in_place.

q_increment :: QDInt -> Circ QDInt

Boxed analogue of q_increment.

Other arithmetic functions

fprealq_of_QDInt_with_shape :: FPRealQ -> QDInt -> Circ (QDInt, FPRealQ)

Turn a QDInt into an FPRealQ, with shape specified by another FPRealQ

q_div2 :: QDInt -> Circ QDInt

Divide a QDInt by 2, in place. (Behavior on odd integers: so far, not required.) As this is not required on odd integers, we can assume that the least significant bit is 0, and use an operation equivalent to a right rotate, instead of a right shift. This can be achieved by changing the list indices within the QDInt, and not a quantum operation, but this operation is *NOT* controllable.

q_square :: QDInt -> Circ (QDInt, QDInt)

Square a QDInt. This is achieved by creating a copy of the input, using the out of place multiplier, and then uncopying the input.

q_gt_param :: QDInt -> IntM -> Circ (QDInt, Qubit)

Test whether a QDInt is (strictly) greater than a parameter IntM.

q_ge_param :: QDInt -> IntM -> Circ (QDInt, Qubit)

Test whether a QDInt is greater than or equal to a parameter IntM.

q_mod_semi_signed :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt)

q_mod_semi_signed x y: reduce x modulo y. x is treated as signed, y as unsigned.

Note: not non-linear safe in x.

q_mod_with_max :: QDInt -> QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt, QDInt)

q_mod_with_max x y m: reduce x modulo y, into the range max – y < x' ≤ max. (Compare mod_with_max.)

q_mod_2times_buggy :: QDInt -> QDInt -> Circ (QDInt, QDInt, QDInt)

Obsolete function, retained for testing since it evokes a subtle bug in with_computed.

Looping combinators

q_bounded_while_with_garbage

Arguments

:: (QData qa, QCData qb)

=> (qa -> Circ (qa, Qubit))

the conditional test on the data

-> Int

a bound on the number of times the loop can run

-> qa

the starting value

-> (qa -> Circ (qa, qb))

the body of the loop

-> Circ (qa, qa)

the initial and final values, and the produced data

Perform a bounded while loop, whose body may produce extra output.

q_bounded_while

Arguments

:: QCData qa

=> (qa -> Circ (qa, Qubit))

the conditional statement

-> Int

a bound on the number of times the loop can run

-> qa

the starting value

-> (qa -> Circ qa)

the body of the loop

-> Circ (qa, qa)

return the initial value, and the final post-loop value

Perform a bounded-length while loop, with an endo-typed body.

Note: uses 2 * bound ancillas. Can this be avoided?

q_bounded_while_productive

Arguments

:: (QCData qa, QCData qb)

=> (qa -> Circ (qa, Qubit))

the conditional test on the data

-> Int

a bound on the number of times the loop can run

-> qa

the starting value

-> (qa -> Circ (qa, qb))

the body of the loop

-> Circ (qa, qa, [qb])

the initial and final values, and the produced data

Perform a bounded while loop, whose body may produce extra output.

q_do_until

Arguments

:: QCData qa

=> Int

a bound on the number of times the loop can run

-> qa

the starting value

-> (qa -> Circ (qa, Qubit))

the body of the loop, producing an input to the next iteration, plus a qubit to mark if we’re finished yet.

-> Circ (qa, qa)

return the initial and final values

Perform a bounded “do_until” loop.