Quipper.Algorithms.CL.Main

Authors: Keith Kim, Peter LeFanu Lumsdaine, Alexandr Virodov

An implementation of Hallgren’s Class Number algorithm. This algorithm computes various invariants of a real quadratic number field K = ℚ(√Δ), notably the class number and the structure of the class group CL(K). The field K is specified by its discriminant Δ, the main input to the algorithm.

The algorithm may also be adapted to other problems from algebraic number theory, including Pell's equation (finding integer solutions to x ² − dy ² = 1, for non-square d) and the principal ideal problem (determining whether an ideal of a number field is principal, and finding a generator if so).

The present implementation falls into five stages, which we will refer to throughout the documentation:

1. Approximate the regulator of K, to low precision, using a version of the the (quantum) HSP algorithm.
2. Classically, refine the approximation from part 1 to higher precision.
3. Classically compute a small generating set for the class group, using the value of the regulator from part 2.
4. Compute relations for these generators, again using a version of the HSP algorithm.
5. Classically compute from these the structure of the class group, and hence the class number.

Further details are given in the documentation of individual modules.

The algorithm and its mathematical background are described in:

• Sean Hallgren, "Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem", in STOC ’02: Proceedings of the thirty-fourth annual ACM symposium on Theory of computing, pp. 653–658, 2002. (Also published in J. ACM, 54(1), 2007.)
• Richard Jozsa, "Quantum computation in algebraic number theory: Hallgren’s efficient quantum algorithm for solving Pell’s equation." Annals of Physics, 306:241–279, February 2003; also available as http://arxiv.org/abs/quant-ph/0302134. All references in documentation refer to arXiv version.
• Daniel Haase and Helmut Maier, "Quantum algorithms for number fields." Fortschr. Phys., 54(8):866–881, 2006.

The present implementation is based on a detailed algorithm specification that was provided to us by the IARPA QCS program and written by Brian J. Matt, Durward McDonell, and David Zaret.

Modules:

• Quipper.Algorithms.CL.Main: Command line interface.
• Quipper.Algorithms.CL.Auxiliary: General-purpose functions required in Hallgren’s algorithm.
• Quipper.Algorithms.CL.Types: Specialized classical and quantum datatypes used in Hallgren’s algorithm, and basic functions on these types.
• Quipper.Algorithms.CL.CL: The high-level structure of Hallgren’s algorithm.
• Quipper.Algorithms.CL.RegulatorClassical: A classical implementation of the functions and operations of stages 1–4.
• Quipper.Algorithms.CL.RegulatorQuantum: A quantum implementation of the functions required for stages 1 and 4
• Quipper.Algorithms.CL.SmithReduction: Matrices, and reduction to Smith Normal Form, for Stage 5.
• Quipper.Algorithms.CL.Test: Functions to test components of the present implementation, using classical computation.

Command line interface

This module provides a command line interface for Hallgren’s Class Number algorithm. This allows the user, for example, to print or simulate the circuits used in quantum portions of the algorithm, or to run small instances of the algorithm in a classical implementation.

Sample invocations:

>>> ./cl -R

Compute, classically, the regulator of ℚ[√Δ], with Δ = 28 (default value).

>>> ./cl -P -d 17

Compute, classically, the fundamental solution of Pell’s equation x² − dy² = 1 with d = Δ = 17.

>>> ./cl -S fn -d 5 -f eps > cl_fn_d5.eps

Produce an .eps file of the quantum circuit implementing the pseudo-periodic function f_N used for regulator estimation, for Δ = 5

>>> ./cl -S starprod -d 60 -f gatecount

Give gate-count for the quantum circuit implementing the star-product on ideals, for Δ = 17

>>> ./cl --help

Print detailed usage information.

Option processing

data WhatToShow

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

Constructors

Stage1

Show the circuit for stage 1 of the algorithm

Stage4

Show the circuit for stage 4 of the algorithm

Sub

Show the circuit for a specific quantum subroutine

Regulator

Classically, find the regulator

FundamentalUnit

Classically, find the fundamental unit

PellSolution

Classically, find the fundamental solution of Pell’s equation

Instances

Show WhatToShow

Defined in Quipper.Algorithms.CL.Main

Methods

showsPrec :: Int -> WhatToShow -> ShowS

show :: WhatToShow -> String

showList :: [WhatToShow] -> ShowS

data Subroutine

An enumeration type for selecting a subroutine.

Constructors

Rho

RhoInv

Normalize

DotProd

StarProd

FN

Instances

Bounded Subroutine

Defined in Quipper.Algorithms.CL.Main

Methods

minBound :: Subroutine

maxBound :: Subroutine

Enum Subroutine

Defined in Quipper.Algorithms.CL.Main

Methods

succ :: Subroutine -> Subroutine

pred :: Subroutine -> Subroutine

toEnum :: Int -> Subroutine

fromEnum :: Subroutine -> Int

enumFrom :: Subroutine -> [Subroutine]

enumFromThen :: Subroutine -> Subroutine -> [Subroutine]

enumFromTo :: Subroutine -> Subroutine -> [Subroutine]

enumFromThenTo :: Subroutine -> Subroutine -> Subroutine -> [Subroutine]

Show Subroutine

Defined in Quipper.Algorithms.CL.Main

Methods

showsPrec :: Int -> Subroutine -> ShowS

show :: Subroutine -> String

showList :: [Subroutine] -> ShowS

subroutine_enum :: [(String, Subroutine)]

An enumeration of available subroutines. (Compare format_enum, gatebase_enum.)

data Options

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

Constructors

Options

Fields

• what :: WhatToShow

  What kind of thing to output.

• format :: Format

  The output format.

• gatebase :: GateBase

  What kind of gates to decompose into.

• sub :: Subroutine

  Which subroutine to output (if what == Sub).

• cl_delta :: CLIntP

  The discriminant Δ, specifying the problem.

• cl_i :: Int

  i, log_2 of the estimated bound 2^i for the weak period S.

• cl_r :: CLReal

  The (good) approximation R of the period.

• cl_q :: CLIntP

  The parameter q for stage 4 of the algorithm.

• cl_k :: CLIntP

  The parameter k for stage 4 of the algorithm.

• cl_n :: CLIntP

  The parameter n for stage 4 of the algorithm.

• cl_m :: CLIntP

  The parameter m for stage 4 of the algorithm.

• cl_generators :: [IdealRed]

  A generating set for CL(K).

• cl_seed :: Int

  The seed for the random generator (0 for seed from time)

Instances

Show Options

Defined in Quipper.Algorithms.CL.Main

Methods

showsPrec :: Int -> Options -> ShowS

show :: Options -> String

showList :: [Options] -> ShowS

default_options :: Options

The default options.

show_default :: Show a => (Options -> a) -> String

Show the default value of an option.

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

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

dopts :: [String] -> IO Options

Process argv-style command line options into an Options structure.

usage :: IO ()

Print usage message to standard output.

The CL circuit generation main function

main :: IO ()

Main function: read options, then execute the appropriate task.

main_stage1 :: Options -> IO ()

Main function for outputting the circuit for stage 1 of Hallgren’s algorithm.

main_stage4 :: Options -> IO ()

Main function for outputting the circuit for stage 4 of Hallgren’s algorithm.

main_sub :: Options -> IO ()

Main function for outputting the circuits for specific subroutines.