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

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

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.