Quipper.Algorithms.USV.Definitions

This module provides global definitions for the Unique Shortest Vector algorithm.

Types for the Unique Shortest Vector algorithm

type TwoPoint = (Qubit, [QDInt])

An input to tPP: a pair of a Qubit and a list of QDInts. Holds a superposition of two vectors with an unknown fixed difference.

type CosetState = (Qubit, QDInt)

An input to dCP: a pair of a Qubit and a QDInt. Holds a superposition of two numbers with an unknown fixed difference.

type Psi_k = (Qubit, Int)

An input to sieving: a pair of a Qubit and an integer. Holds a state of the form:

together with the integer k.

General purpose functions

concat_pair :: ([a], [b]) -> ([a], [b]) -> ([a], [b])

Concatenate two pairs of lists componentwise.

multi_split :: StdGen -> [StdGen]

Construct a list of random number generators.

find :: [a] -> (a -> Bool) -> String -> (a, [a])

Given a list l, a predicate p and an error message msg, return a pair (a,l') where a is the first element of l satisfying p and l' is the remaining list. If no such element exists, raise an error and display msg.

separate :: [a] -> (a -> Bool) -> ([a], [a])

Given a list l and a predicate p, return a pair (l1, l2) where l1 contains the elements of l satisfying p and l2 the others.

expand :: Integer -> Integer -> [Integer]

Given integers m and n, compute the big-endian expansion of m in base n.

qdiscard_psi_ks :: [Psi_k] -> Circ ()

Discard a list of Psi_ks

find_partners :: Ord b => (a -> b) -> [a] -> ([(a, a)], [a])

Given a list of people, and a function assigning a religion to each person, divide the people into couples of the same religion. Some people will remain single if there isn't a suitable partner. Return a list of couples and a list of single people.

The algorithm proceeds as follows. We have a room for each religion. Initially the rooms are empty. As each person arrives, they go to their room. If the room is empty, they stay there. If the room is occupied, they marry the occupant and join the list of couples. At the end, all single people are retrieved from their rooms.

This function is lazy, i.e., couples are formed as they are found. Only the singles have to wait until the end of the list.

Running time is O(n log n).

Linear algebra

norm :: [Integer] -> Float

Compute the Euclidean norm of a vector.

vector_add :: Num a => [a] -> [a] -> [a]

Compute the sum of two vectors.

q_vector_add :: [QDInt] -> [QDInt] -> Circ [QDInt]

Quantum version of vector_add.

scalar_mult :: Num a => a -> [a] -> [a]

Compute the multiplication of a scalar with a vector.

q_scalar_mult :: QDInt -> [QDInt] -> Circ [QDInt]

Quantum version of scalar_mult.

matrix_mult :: [[Integer]] -> [Integer] -> [Integer]

Multiply an n×m-matrix by an m-dimensional column vector to obtain an n-dimensional column vector. The matrix is represented as a list of m columns.

Precondition: m > 0.

Example:

matrix_mult [[1,2,3],[1,0,0]] [1,1] = [2,2,3]

q_matrix_mult :: [[QDInt]] -> [QDInt] -> Circ [QDInt]

Quantum version of matrix_mult.

is_zero_vector :: [Integer] -> Bool

Check whether a vector is 0.

Euclid's algorithm

ext_euclid :: Integer -> Integer -> (Integer, Integer, Integer, Integer, Integer)

The extended Euclidean algorithm. ext_euclid a b returns (x, y, z, w, d) such that:

• 0 ≤ d = gcd(a, b), the greatest common divisor of a and b;
• ax + by = d;
• az + bw = 0;
• the determinant xw - yz = 1.

Classical subroutines

lll :: [[Integer]] -> [[Integer]]

Reduce a basis using the Lenstra-Lenstra-Lováscz algorithm.

Uses the corresponding Haskell library.

find_prime :: Int -> Int

Given an integer m, find the smallest prime p such that m ≤ p ≤ 2m.

Uses preexisting isPrime algorithm.

is_in_lattice :: [Integer] -> [[Integer]] -> Bool

Given a vector u and a basis bb = [b₀, …, b_n-1], determine whether u belongs to the lattice generated by bb, i.e., whether there exist integers a₀, …, a_n-1 such that u = a₀b₀ + … + a_n-1b_n-1.

Precondition: u and b₀, …, b_n-1 must all be of the same dimension.

The algorithm proceeds as follows: first, do invertible integer column operations on b₀, …, b_n-1 until the top entries of b₁, …, b_n-1 are 0. This can be done efficiently by using the extended Euclidean algorithm for two columns at a time. Then check whether the top entry of b₀ divides the top entry of u. If no, output False. Otherwise, if the top entry of b₀ is 0, drop the top row and continue recursively. Otherwise, subtract an appropriate multiple of b₀ from u, drop b₀, drop the top row, and continue recursively. Trivial base cases occur when the number of rows or columns reaches 0.

reduce_lattice :: [[Integer]] -> [[Integer]]

Given a basis bb = [b₀, …, b_n-1], find another equivalent basis whose elements are linearly independent.

column_op :: [Integer] -> [Integer] -> ([Integer], [Integer])

Perform a reversible column operation on two integer vectors, creating (and then dropping) a leading zero in the second vector.