Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Recovering the Period in Shor's Algorithm with Gauss' Algorithm for
  Lattice Basis Reduction   Shor's algorithm contains a classical post-processing part for which we aim
to create an efficient, understandable method aside from continued fractions.
  Let r be an unknown positive integer. Assume that with some constant
probability we obtain random positive integers of the form x=[ N k/r ] where
[.] is either the floor or ceiling of the rational number, k is selected
uniformly at random from {0,1,...,r-1}, and N is a parameter that can be
chosen. The problem of recovering r from such samples occurs precisely in the
classical post-processing part of Shor's algorithm. The quantum part (quantum
phase estimation) makes it possible to obtain such samples where r is the order
of some element a of the unit group of Z_n and n is the number to be factored.
  Shor showed that the continued fraction algorithm can be used to efficiently
recover r, since if N>2r^2 then k/r appears in lowest terms as one of the
convergents of x/N due to a standard result on continued fractions. We present
here an alternative method for recovering r based on the Gauss algorithm for
lattice basis reduction, allowing us to efficiently find the shortest nonzero
vector of a lattice generated by two vectors. Our method is about as efficient
as the method based on continued fractions, yet it is much easier to understand
all the details of why it works.

29
The categories of this paper are: funct-an
14
The categories of this paper are: math-ph
10
The categories of this paper are: q-bio
28
The categories of this paper are: alg-geom
23
The categories of this paper are: solv-int
2
The categories of this paper are: math
12
The categories of this paper are: nucl-th
24
The categories of this paper are: dg-ga
36
The categories of this paper are: cmp-lg
8
The categories of this paper are: hep-ex
30
The categories of this paper are: q-alg
3
The categories of this paper are: physics
11
The categories of this paper are: hep-lat
5
The categories of this paper are: gr-qc
35
The categories of this paper are: mtrl-th
21
The categories of this paper are: adap-org