The Quipper System

Safe HaskellNone

Algorithms.USV.Main

Contents

Description

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 n3. 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:

Synopsis

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.

Constructors

F

Show f_quantum. Depends on input b.

G

Show g_quantum. Depends on input b.

H

Show h_quantum. Depends on input n.

USVP

Run uSVP. Depends on input b.

Q

Run algorithm_Q. Depends on input b.

R

Show algorithm_R. Depends on input b.

TPP

Run tPP. Depends on input n.

Sieve

Run sieving. Depends on input n.

DCP

Run dCP. Depends on input n.

Test

Run Simulation test for h_quantum. Depends on input n.

data Options Source #

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

Constructors

Options 

Fields

Instances

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.

usage :: IO () Source #

Print usage message to stdout.

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

Parse a string to a list of integers, or return Nothing on failure.

Main function

main :: IO () Source #

The main function for the Unique Shortest Vector problem: read options, then execute the appropriate task.