Safe Haskell | None |
---|

Author: Neil Julien Ross

An implementation of the Unique Shortest Vector (USV)
algorithm. The input to the Unique Shortest Vector
problem is an *n*×*n* integer matrix *B* with
the property that the lattice *L(B)* spanned by *B*
contains a unique vector *u* such that that any
other non-parallel vector *v* in the lattice is
longer then *u* by a factor of *n*^{3}. The
output is the vector *u*.

The algorithm proceeds in two steps: first it uses Regev’s method to reduce the USV to the Two Point problem (TPP) and then to the Dihedral Coset problem (DCP), second it uses Kuperberg’s algorithm to solve the DCP. The first step transforms the input matrix into a set of coset states by partitioning the space into hypercubes containing at most two lattice points, and then collapsing the space onto one such cube. The second step uses a sieving method on the obtained set of coset states to extract the shortest vector.

These algorithms are described in:

- G. Kuperberg, "A subexponential-time quantum
algorithm for the dihedral hidden subgroup problem."
*SIAM J. Comput.*35(1):170-188,2005. - O. Regev, "Quantum computation and lattice problems."
In Danielle C. Martin, editor,
*Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science*, pp. 520-529, Nov. 16-19, Vancouver, BC, Canada, 2002. IEEE, IEEE Press, Los Alamitos, CA.

The present implementation is based on a detailed algorithm specification that was provided to us by the IARPA QCS program and written by Andrew J. Landahl.

Modules:

- Algorithms.USV.Main: Command line interface.
- Algorithms.USV.Definitions: Some general-purpose definitions.
- Algorithms.USV.USV: The implementation of the main Unique Shortest Vector algorithm.
- Algorithms.USV.Simulate: Functions for testing and debugging certain subroutines.

# Command line interface

This module provides a command line interface for the Unique
Shortest Vector algorithm. This allows the user, for example, to
show different parts of the circuit, select a gate base,
select parameters such as *n* and *b*, and select different output
formats.

- Example invocations:

./usv

Default options: the `sieving`

algorithm with
*n*=5 and ASCII output format. Because the `sieving`

algorithm uses the `dynamic_lift`

function, the user
will be prompted to provide values corresponding to
a hypothetical measurement outcome (0 or 1) .

./usv -F -f gatecount

The gate count for `f_quantum`

.

- Options and parameters:

*b*is the lattice basis (Default value: a 5×5 matrix with entries set to 1).*n*is the dimension of the lattice (Default value: 5).*s*is the seed for the random number generator (Default value: 1).

- Restrictions:

The `sieving`

algorithm uses the `dynamic_lift`

function.
The only output format that currently supports such a
functionality is ASCII. All algorithms that call
`sieving`

must therefore be run with the default
(ASCII) output format. These are: `sieving`

, `dCP`

, `tPP`

,
`algorithm_Q`

and `uSVP`

.

# Option processing

data WhatToShow Source #

An enumeration type for determining what the main function should do.

F | Show |

G | Show |

H | Show |

USVP | Run |

Q | Run |

R | Show |

TPP | Run |

Sieve | Run |

DCP | Run |

Test | Run Simulation test for |

A data type to hold values set by command line options.

defaultOptions :: Options Source #

The default options.

options :: [OptDescr (Options -> IO Options)] Source #

The list of command line options, in the format required by `getOpt`

.

dopts :: [String] -> IO Options Source #

Process *argv*-style command line options into an `Options`

structure.

parse_list_basis :: String -> Maybe [[Integer]] Source #

Parse a string to a list of integers, or return `Nothing`

on failure.