THE HIDDEN SUBGROUP PROBLEM - REVIEW AND OPEN PROBLEMS

CHRIS LOMONT, CYBERNET

Abstract. An overview of quantum computing and in particular the Hidden Subgroup Problem are presented from a mathematical viewpoint. Detailed proofs are supplied for many important results from the literature, and notation is unified, making it easier to absorb the background necessary to begin research on the Hidden Subgroup Problem. Proofs are provided which give very concrete algorithms and bounds for the finite abelian case with little outside references, and future directions are provided for the nonabelian case. This summary is current as of October 2004.

Contents

1. Introduction 2 1.1. Importance 2 1.2. History 2 1.3. Notation 3 1.4. Layout 3 2. Quantum Computing Model 3 2.1. The Rules and Math of Quantum Mechanics 3 2.2. Efficient Quantum Computation 6 3. The Abelian Hidden Subgroup Problem 10 3.1. Definition of the Hidden Subgroup Problem 10 3.2. The Fast Fourier Transform 11 3.3. The Basic Example 11 3.4. Computing the Fourier Transform on ℤ_{N} Efficiently 13 3.5. The General Finite Abelian Group 17 3.6. The Standard Problems 23 3.7. Conclusion 24 4. The General Hidden Subgroup Problem 25 4.1. Importance 25 4.2. Representation Theory Overview 25 4.3. The General Fourier Transform 27 4.4. The Standard HSP Algorithm - Quantum Fourier Sampling 28 5. Nonabelian Results 30 5.1. Overview 30 5.2. A Necessary Result 30 5.3. The Dihedral Group D_{N} 31 5.4. Groups with an Efficient QFT 33 5.5. HSP Algorithms and Groups 34 5.6. Black-Box Group Algorithms 37 5.7. Hidden Subgroups are Distinguishable 42 6. Conclusion 43 6.1. Other Quantum Algorithms 44 Appendix A. The Cyclic Quantum Fourier Transform over ℤ_{N} 45 A.1. The Quantum Fourier Transform over ℤ_{2^{n}} 45 A.2. The Quantum Fourier Transform over ℤ_{N}, N Odd 46 Appendix B. Graph Reductions 61 B.1. Basic Graph Algorithm Relations 61 B.2. Quantum HSP for Graph Isomorphism 64 Appendix C. Quantum Mechanics Details 64 C.1. The Rules and Math of Quantum Mechanics 64 Appendix D. Random Group Generation 76 Appendix E. GCD Probabilities 77 References 79

Date: Oct 2004.

clomont@cybernet.com, clomont@math.purdue.edu.

1. Introduction

The main purpose of this paper is to give a self contained explanation of the Hidden Subgroup Problem in quantum computing. A second goal is to bring the interested reader to the forefront of research in the area, so that a wider audience can attack the problems. The final goal is to present this at a level accessible to graduate students in math, physics, and computer science. Prerequisites are some abstract algebra, linear algebra, and an understanding of (classical) computation. However almost any mathematically inclined reader should be able to learn something from this presentation.

1.1. Importance. The importance of the Hidden Subgroup Problem (from now on labelled the HSP) is that it encompasses most of the quantum algorithms found so far that are exponentially faster than their classical counterparts. Research in this area is centered on extending the families of groups for which the HSP can be efficiently solved, which may improve other classically inefficient algorithms, such as determining graph isomorphism or finding the shortest vector in a lattice. Finally, there are many group theoretic algorithms that are more efficient on a quantum computer, such as finding the order of a finite group given a set of generators.

1.2. History. In 1994, Shor [114], building on the work of Deutsch [37] and Simon [118], found a quantum algorithm that could factor integers exponentially faster than any known classical method, and opened the floodgates on quantum computing research. Efficient integer factoring breaks the ubiquitous RSA cryptosystem. Shor also gave an algorithm solving the Discrete Log Problem (DLP), which is used in several other cryptosystems. Kitaev [77] noted that these algorithms as well as others fit in a framework of finding subgroup generators from a group using a function that “hides” the subgroup, and thus the Hidden Subgroup Problem was born. For more history, the book by Chuang and Neilsen [29] contains a wealth of information, as well as the quantum physics archives at

http://arxiv.org/archive/quant-ph.

1.3. Notation. Here we fix some notation used throughout this paper. All logs are base 2 unless otherwise specified. ℂ denotes the field of complex numbers. ℤ is the ring of integers, and for a positive integer N we let ℤ_{N} denote the ring of integers mod N. For each integer N > 0 let ω_{N} = exp(2πi/N), a principal N^{th} root of unity. Quantum mechanics specific notation is in section 2 and appendix C.

1.4. Layout. The layout of this paper is as follows. Section 2 covers the necessary quantum mechanics and notation used therein. It also introduces a quantum computing model well suited to present the rest of the topics in this paper. Section 3 explains the algorithm solving the abelian case of the HSP efficiently, describing in detail the mathematics making it work. Section 4 generalizes the examples from section 3 to give the a more general form of the HSP, suitable for any finite group. Section 5 covers recent results, and what is currently known about the HSP, as well as quantum algorithms for other group related problems. Section 6 concludes. Much of the background and details are included in numerous appendices, giving details on topics such as the necessary background for the graph isomorphism reduction, generating groups from random samples, number theory results, etc.

2. Quantum Computing Model

2.1. The Rules and Math of Quantum Mechanics. Here we define the rules of quantum mechanics (from a mathematical perspective). Details can be seen in Appendix C.

First some notation used in quantum mechanics. We define the following symbols:

|ψ⟩ represents a column vector in some complex Hilbert space V, of finite dimension for this paper. For this section, let this dimension be N. Quantum mechanics forces us to use an orthonormal basis for V, so we fix the orthonormal standard basis B = {|0⟩, |1⟩, …, |N − 1⟩}. Then ⟨ψ| denotes the conjugate transpose row vector, often viewed as the dual to |ψ⟩ with respect to B. For example, we compute as follows:

If |ψ⟩ = ∑_{i} a_{i}|i⟩, then ⟨ψ| = ∑_{i} a_{i}^{∗}⟨i|, where ∗ denotes complex conjugation. ⟨i| |j⟩, written ⟨i|j⟩, equals 1 if i = j, otherwise ⟨i|j⟩ equals 0. A basis for linear operators on V can be written as a ℂ-linear combination of the operators |i⟩⟨j|, which is the matrix with a 1 in the (i, j) entry, and 0’s elsewhere. Thus any linear operator A on V in the basis B can be written in the form A = ∑_{i,j} a_{i,j}|i⟩⟨j|, which is the matrix with the value a_{i,j} in the i, j entry, and acting on the left of a column vector |ψ⟩. ⟨ψ|A|ϕ⟩ is the inner product of ψ and A|ϕ⟩. Later the basis will often be indexed with elements from a group G, viewed as fixing an orthonormal basis and an injection mapping elements of G to this basis.

2.1.1. The Postulates of Quantum Mechanics. Now on to the physical content of quantum mechanics, abstracted to a mathematical formalism. The content of quantum mechanics can be summarized by 4 postulates, which we take as the definition of quantum mechanics. They are:^{1}

Quantum Mechanics Postulate 1: State Space: Associated to an isolated physical system is a complex vector space with inner product (a Hilbert space) known as the state space of the system. The system is completely described by its state vector, which is a unit vector in the system’s state space.

1Postulates are taken verbatim from Neilsen and Chuang [29].

Quantum Mechanics Postulate 2: State Evolution: The evolution of a closed quantum system is described by a unitary transformation^{2}. That is, the state of a system |ψ⟩ at time t_{1} is related to the state |ψ′⟩ at time t_{2} by a unitary operator U which depends only on the times t_{1} and t_{2},

(1)  |ψ⟩ = U|ψ′⟩

Quantum Mechanics Postulate 3: State Measurement: Quantum measurements are described by a collection {M_{m}} of measurement operators. These are operators acting on the state space of a system being measured. The index m refers to the measurement outcomes that may occur in the experiment. If the state of the system is |ψ⟩ immediately before the measurement, then the probability that result m occurs is given by

(2)  p(m) = ⟨ψ|M_{m}^{†}M_{m}|ψ⟩

and the state of the system after the measurement is

(3)  \frac{M_{m}|ψ⟩}{\sqrt{p(m)}}

The measurement operators satisfy the completeness equation

(4)  ∑_{m} M_{m}^{†}M_{m} = I

Quantum Mechanics Postulate 4: State Combining: The state space of a composite physical system is the tensor product of the state spaces of the component systems. Moreover, if we have systems numbered 1 through n, and system number j is prepared in the state |ψ_{j}⟩, then the joint state of the total system is |ψ_{1}⟩ ⊗ |ψ_{2}⟩ ⊗ … |ψ_{n}⟩.

We will explain briefly how these postulates are used in practice for quantum computing.

2.1.2. Qubits and Operators. Analogous to the bit being the basic block in classical computing, the qubit is the basic building block in quantum computing. Formally we define

Definition 2.1 (Qubit). A qubit (or quantum-bit) is a unit vector in ℂ^{2}. We fix

an orthonormal basis of column vectors denoted as |0⟩ = ( \begin{matrix}1 \\ 0 \end{matrix} ) and |1⟩ = ( \begin{matrix}0 \\ 1 \end{matrix} ),

corresponding to classical bits 0 and 1.

Definition 2.2 (State vector). The state of a quantum system is a (column) vector in some vector space, written |ψ⟩.

By postulate 4, we can combine single qubits as follows.

2Recall a unitary operator U satisfies UU^{†} = I = U^{†}U where † is conjugate transpose. In particular, unitary operators are invertible, implying quantum computation is reversible, which differs significantly from classical computing.

2.1.3. Qubits Galore. Similar to concatenating n classical bits to “bitstrings”, we concatenate qubits to get larger systems. Two qubits form a space spanned by the four vectors

(5)  |0⟩ ⊗ |0⟩, |0⟩ ⊗ |1⟩, |1⟩ ⊗ |0⟩, and |1⟩ ⊗ |1⟩

where the tensor product is the usual vector space tensor. See Appendix C for details. Shorthand for the above expressions is

(6)  |00⟩, |01⟩, |10⟩, and |11⟩

Now we can check the second basis element (dictionary ordering)

(7)  |01⟩ = |0⟩ ⊗ |1⟩

= \binom{1}{0} ⊗ \binom{0}{1} (8)

(9)  = (\begin{matrix}1\binom{0}{1} \\ 0\binom{0}{1} \end{matrix}) = (\begin{matrix}0 \\ 1 \\ 0 \\ 0 \end{matrix})

and we get the second usual basis element of ℂ^{4}. This works in general; that is, the vector corresponding to the state |n⟩ where n is a binary number, is the (n + 1)^{th} standard basis element. We frequently use decimal shorthand: |32⟩ is the 33rd standard basis vector in some space which would be clear from context.

Thus the the state of an n-qubit system is a unit vector in ℂ^{2^{n}}. Note that the state of n classical bits is described by n elements each either 0 or 1, while the state of n qubits requires 2^{n} complex numbers to describe. Thus it seems qubits contain much more “information” than classical bits. Unfortunately we cannot retrieve all this “information” from the state; we are limited by quantum mechanics due to the fact that measuring the state destroys information.

2.1.4. Measurement. The final operation we need to understand about qubits is measurement, the process of getting information out of a quantum state. There are several equivalent ways to think about it. We will cover the easiest to understand, intuitively and mathematically. However, to gain precise control over measurements, often one has to resort to an equivalent, yet more complicated, measurement framework^{3}, which we do not discuss here. See Nielsen and Chuang [29, Ch. 2].

We will do our measurements in the computational basis {|0⟩, |1⟩, …, |2^{n} − 1⟩} over an n-qubit system. Suppose we have the state |ψ⟩ = ∑_{j=0}^{2^{n}−1} a_{j}|j⟩, which is a unit vector in ℂ^{2^{n}}. Measuring in the computational basis has the following effect: it returns the state |j⟩ with probability p_{j} = |a_{j}|^{2}, and after the measurement, the state becomes |ψ′⟩ = |j⟩. Thus measuring “collapses” the waveform, returning a state with probability the square of its coefficient (amplitude), and the resulting state is the one returned by the measurement. Thus from a given state, we return one answer depending on the basis we measure, and destroy all other information about the state.

Finally we note that cascaded measurements (one after the other) can always be replaced by a single measurement.

3This is the “Positive Operator-Valued Measure” (POVM) formalism.

2.1.5. The No Cloning Theorem. As an example of the using above postulates, we prove an important and surprising theorem:

Theorem 2.3. The No Cloning Theorem. It is impossible to build a machine that can clone any given quantum state.

This is in stark contrast to the classical case, where we copy information all the time. It is the tip of the iceberg for the differences between quantum and classical computing.

Proof. Suppose we have a machine with two slots: A for the quantum state |ψ⟩ to be cloned, and B in some fixed initial state |s⟩, and the machine makes a copy of the quantum state A. By the rules of quantum mechanics, the evolution U is unitary, so we have

(10)  |ψ⟩ ⊗ |s⟩ ⟶^{U} |ψ⟩ ⊗ |ψ⟩

Now suppose we have two states we wish to clone, |ψ⟩ and |φ⟩, giving

U (|ψ⟩ ⊗ |s⟩) = |ψ⟩ ⊗ |ψ⟩
U (|φ⟩ ⊗ |s⟩) = |φ⟩ ⊗ |φ⟩

Taking the inner product of these two equations, and using U^{†}U = I:

(⟨φ| ⊗ ⟨s|) U^{†}U (|ψ⟩ ⊗ |s⟩) = (⟨φ| ⊗ ⟨φ|) (|ψ⟩ ⊗ |ψ⟩)
⟨φ|ψ⟩⟨s|s⟩ = ⟨φ|ψ⟩⟨φ|ψ⟩
⟨φ|ψ⟩ = (⟨φ|ψ⟩)^{2}

This has solutions if and only if ⟨φ|ψ⟩ is 0 or 1, so cloning cannot be done for general states.^{4} □

2.2. Efficient Quantum Computation.

2.2.1. Quantum Computing. Quantum sates are transformed by applying unitary operators to the state. So where classical computing can be viewed as applying transforms to n-bit systems, quantum computation proceeds by constructing an n-qubit machine, applying unitary operators to the state until some desired state is found, and then measuring the result. This paper will avoid the physical construction of such machines, and focus on the unitary transformations that seem likely to be physically realizable, and the computational outcomes of such systems. Again, for an introduction to the physical issues, see [29, Ch. 7] and the references therein.

2.2.2. Circuit Model. Similar to being able to construct any classical circuit with NAND gates, there are finite ^{5} sets of quantum gates that allow the construction of any unitary operator to a desired precision. Kitaev [78] shows that these approximations can be done with minimal overhead, allowing quantum computation to be modelled with simple “quantum circuits”. A final note on quantum circuits is that Deutsch’s Quantum Turing Machine [37] and the circuit model used more recently were shown equivalent by Yao [128]. We will use a few quantum gates that operate on 1,2, or 3 qubits at a time, defined later. The intuitive description is that quantum computations are built of quantum circuits, which are composed of quantum gates, and each quantum gate operates on only a few qubits at a time. This statement mirrors the classical one with “quantum” removed and qubits replaced with bits.

4There is a lot of research on precisely what can be cloned, how to approximate cloning, and what other limitations there are to duplicating quantum states.

5There are many ways to choose them. See for example [8].

2.2.3. Quantum Circuit Size. In loose terms, efficient classical computations are done on small circuits, in the sense that as the problem size grows, the size of the circuit required to solve the problem grows at a certain rate, usually bounded polynomially in the size of the problem. We want to make this precise in the quantum context.

The following is just a mathematically precise way to say our “elementary operations” only operate on a few qubits at a time, which is desirable since it makes quantum computation physically plausible. Some definitions:

Definition 2.4. Given a 2^{n}-dimensional vector space V with basis B, and a 2^{m}×2^{m} matrix U with m ≤ n, an expansion of U relative to B is any matrix of the form G(U ⊗ I_{2^{n−m}})G^{−1} where G permutes the basis, and I_{k} is the k × k identity matrix.

This just says each expansion of U operates on m of the n qubits in a n-qubit machine. In general m will be small, n will vary, and we will build computations by composing these operators.

Definition 2.5. Given a 2^{n}-dimensional vector space V, an orthonormal basis B of V, and a finite set U = {U_{1}, U_{2}, … U_{k}} of unitary matrices of dimensions dividing 2^{n}, then the set of elementary operations relative to (B, U) consists of all expansions of the U_{i} relative to B.

This just allows us to consider all operations on any subset of n qubits generated from our initial set of “elementary operations”. Note U unitary and B orthonormal implies expansions of U relative to B are unitary.

For our use V will be the state space of a quantum system, clear from context, and B will be the standard orthonormal basis of V. We fix a specific generating set U_{τ} = {H, CNOT, CCNOT, P } relative to such a fixed basis to be the matrices

(11)  H = \frac{1}{2} (\begin{matrix}1 & 1 \\ 1 & −1 \end{matrix}) the Hadamard matrix

(12)  CNOT = (\begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix}) the controlled NOT

(13) CCNOT = (a_{ij}) with a_{ii} = 1, i = 1, ..., 6, a_{87} = a_{78} = 1,

the rest = 0, the controlled controlled NOT

(14)  P = (\begin{matrix}e^{i \frac{θ}{2}} & 0 \\ 0 & e^{−i \frac{θ}{2}} \end{matrix} ) the phase matrix, where cos θ = \frac{3}{5}.

For any n > 2 and using the standard basis B defined earlier, the elementary operations from this set of 4 matrices generates a group dense in U(2^{n}), the space of legal quantum operations on an n-qubit machine^{6}. So from now on one can assume these 4 matrices and associated elementary operations are the legal set of elementary operations on any n-qubit machine. The definitive paper on elementary gates for quantum computing is [8].

6From chapter 4 exercises in [29].

Definition 2.6. A quantum circuit is a unitary matrix built from composing elementary operations from U_{τ}

Now mathematically, quantum computing becomes the following. We have an initial state |0⟩ in the n-qubit space ℂ^{2^{n}}. Applying unitary transformations that are products of the elementary transformations, we want to obtain a quantum state (unit vector |ψ⟩) that, when measured, has a high probability of returning some useful answer. We want to know how “efficient” such transformation are. We restrict legal quantum operations to those obtained from the elementary operations from some finite set, such as U_{τ}.

Definition 2.7. The size of a quantum circuit will be the minimal number of elementary operations composed to obtain it.

This gives us a way to measure the complexity of a quantum operation. From here on we can assume all quantum operation complexities are measured against our set of elementary operations coming from U_{τ} and a corresponding V and B taken from context.

Often it is possible to rearrange the elementary operations and obtain the same quantum circuit. For example if adjacent operations affect disjoint sets of qubits, these two operations can be swapped obtaining the same circuit (the matrices commute). Similar to parallelizing classical circuits, this reordering allows us to partition the sequence of elementary operations into ordered lists of operations, where within each list a qubit is affected by at most one operation. This leads to the notion of depth:

Definition 2.8. The depth of a quantum circuit is the minimal length of a partition of the ordered elementary operations composing the circuit into ordered lists where each qubit is affected at most once per list.

As a result, we always have depth≤size.

To parallel the quantum to classical terminology, we sometimes call a state (or part of a state) a quantum register. Physically a quantum state is basically constructed using n particles which can be either of two states 0 or 1 when measured. If we take a subset of these particles, and operate on them, it is convenient to call this subset a register.

Definition 2.9. A register in a quantum computer is a subset of the total set of qubits. We often write |a⟩|b⟩ to denote that the first register is in state |a⟩ and the second in state |b⟩, the number of qubits in each set being understood from context.

2.2.4. Efficient Quantum Computation. Most of this paper is concerned with efficient quantum computation. Sometimes this has two components: needing an efficient quantum process, and an efficient classical computing method to postprocess the data output from the quantum process to obtain the desired answer. We will see these two are (often) separate issues.

Given a problem to solve on a quantum computer, we need a way to represent the problem as a quantum state, a unitary operation U built from elementary operations to convert this quantum state to a final state, and a way to process the final state to obtain the desired answer. Although a precise definition of “efficient” takes us too far afield, we will make it precise in special cases throughout this paper. The general idea is that as the “size” of the input grows (the number of qubits required to represent the problem, say), the size of the necessary quantum operator U should grow polynomially in the size of the input.

An example: suppose we want to determine the order of finite abelian groups given a generating set for each one. Given a group |G|, we can represent each element using roughly log |G| qubits. To call a quantum algorithm efficient for this problem would mean the size of the quantum circuit computing the order of G should be of size polynomial in log |G|, as G varies throughout the family of finite abelian groups.

As a final technical point, we require what is called a “uniform class of algorithms,” meaning that, for a problem of size n, there is a Turing machine that given n, can produce the circuit description in number of steps equal to a polynomial in n. This ensures that we can (in theory) construct an explicit machine to solve each problem in time polynomial in the size of the problem.

For more information on quantum complexity, see [18, 31].

2.2.5. A Note on Probabilistic Algorithms. Quantum computers are probabilistic, meaning that algorithms tend to be of the form “Problem A is solved with probability 80%.” For those used to thinking that algorithms solve problems with certainty (such as algorithms encountered in a first algorithms class), note that probabilistic algorithms suffice in practice. We just run the experiment a few times, and take the majority result. This returns the correct answer with probability exponentially close to 1 in the number of trials. Precisely we use the following theorem:

Theorem 2.10 (The Chernoff Bound). Suppose X_{1}, X_{2}, …, X_{n} are independent and identically distributed random variables, each taking the value 1 with probability 1/2 + ϵ and 0 with probability 1/2 − ϵ. Then

(15)  p (∑_{i=1}^{n} X_{i} ≤ \frac{n}{2}) ≤ e^{−2ϵ^{2}n}.

Thus the majority is wrong very rarely. For example, we will make most algorithms succeed with probability 3/4, so our ϵ = 1/4. Although it sounds like a lot, taking 400 repetitions of the algorithm causes our error to drop below 10^{−20}, at which point it is more likely our computer fails than the algorithm fails. And since the algorithms we are considering are usually exponentially faster than classical ones, there is still a net gain in performance. If we do 1000 runs, our error drops below 10^{−55}, at which point it is probably more likely you’ll get hit by lightning while reading this sentence than the algorithm itself will fail. For completeness, here is a proof of the Chernoff Bound.

Proof. Consider a sequence (x_{1}, x_{2}, …, x_{n}) containing at most n/2 ones. The probability of such a sequence is maximized when it contains ⌊n/2⌋ ones, so

(16)  p (X_{1} = x_{1}, X_{2} = x_{2}, …, X_{n} = x_{n}) ≤ (\frac{1}{2} − ϵ)^{\frac{n}{2}} (\frac{1}{2} + ϵ)^{\frac{n}{2}}

= \frac{(1 − 4ϵ^{2})^{\frac{n}{2}}}{2^{n}} . (17)

There can be at most 2^{n} such sequences, so

(18)  p (∑_{i=1}^{n} X_{i} ≤ \frac{n}{2}) ≤ 2^{n} × \frac{(1 − 4ϵ^{2})^{\frac{n}{2}}}{2^{n}} = (1 − 4ϵ^{2})^{\frac{n}{2}} .

From calculus, 1 − x ≤ exp(−x), so

(19)  p (∑_{i=1}^{n} X_{i} ≤ \frac{n}{2}) ≤ e^{−4ϵ^{2}n/2} = e^{−2ϵ^{2}n}
□

3. The Abelian Hidden Subgroup Problem

We will detail the Hidden Subgroup Problem (HSP), starting with some illustrative and historically earlier examples, before covering the most general cases and research problems. The simplest groups considered are the finite cyclic groups, followed by finite abelian groups. Kitaev [77] examines a similar problem over finitely generated abelian groups, but we will not cover that here. The finite abelian case was first used to spectacular effect by Shor [114] and Simon [118]. The HSP for finite nonabelian groups is currently researched for the reasons given in sections 4 and 5.

Related to the HSP over finite groups is the Abelian Stabilizer Problem, in Kitaev [77].

3.1. Definition of the Hidden Subgroup Problem. In order to set the stage for the rest of the paper, we make a general definition of the Hidden Subgroup Problem, which we will abbreviate HSP for the rest of this paper, and then attempt to determine for which groups G and subgroups H we can solve the HSP efficiently. We will also discuss partial results on groups for which efficient HSP algorithms are not known.

Definition 3.1 (Separates cosets). Given a group G, a subgroup H ≤ G, and a set X, we say a function f : G → X separates cosets of H if for all g_{1}, g_{2} ∈ G, f(g_{1}) = f(g_{2}) if and only if g_{1}H = g_{2}H.

Definition 3.2 (The Hidden Subgroup Problem). Let G be a group, X a finite set, and f : G → X a function such that there exists a subgroup H < G for which f separates cosets of H. Using information gained from evaluations of f, determine a generating set for H.

For any finite group G, a classical algorithm can call a routine evaluating f(g) once for each g ∈ G, and thus determine H with |G| function calls. A central challenge of quantum computing is to reduce this naive O(|G|) time algorithm to O(poly(log |G|)) time (including oracle calls and any needed classical postprocessing time). This can be done for many groups, which gives the exponential speedup found in most quantum algorithms.

We assume an efficient encoding of G and X to basis states of our quantum computer. We also assume a quantum “black-box” that operates in unit time for performing the unitary transform U_{f}|g⟩|x⟩ = |g⟩|x ⊕ f(g)⟩, for g ∈ G, x ∈ X, and ⊕ bitwise addition on the state indices.

3.2. The Fast Fourier Transform. The Fast Fourier Transform (FFT) of Cooley and Tukey [34] reduced the cost of doing Fourier transforms from the naive O(n^{2}) down to O(n log n), allowing a large class of problems to be attacked by computers. Mikhail Atallah^{7} remarked the FFT is the most important algorithm in computer science. The success of the FFT is that so many other problems can be reduced to a Fourier transform, from multiplication of numbers and polynomials to image processing to sound analysis to correlation and convolution^{8}. More references are Beth[19], Karpovsky[72], and Maslen and Rockmore [93].

Most, if not all, quantum algorithms that are exponentially faster than their classical counterparts rely on a quantum Fourier transform (QFT), and much of the rest of this document deals with the QFT. For more information beyond this paper on the QFT see Ekert and Jozsa[42], Hales and Hallgren[56], and Jozsa[68].

Just as the FFT turned out to be a big breakthrough in classical computing, exploiting the QFT so far is the central theme in quantum algorithms. The main reason quantum algorithms are exponentially faster is the QFT can be done exponentially faster than the classical FFT. However there are limitations due to the probabilistic nature of quantum states.

3.3. The Basic Example. Fix an integer N > 1. Let X be a finite set, and let G = ⟨ℤ_{N}, +⟩ be the additive group of integers mod N. Suppose we have a function (set map) f : G → X such that there is a subgroup H = ⟨d⟩ of G, such that f is constant on H and distinct on cosets of H, that is, f separates cosets of H. Let M = |H|. We assume we have a quantum machine^{9} capable of computing the unitary transform on two registers f : |x⟩|y⟩ → |x⟩|f(x)⊕y⟩, where ⊕ is (qu)bitwise addition^{10}. We do not assume we know M or d or H; we only know G and have a machine computing f. We want to determine a generating set for H, calling the “black-box” function f as few times as possible. For now we ignore the size of the quantum circuit and focus on the math making the whole process work. Later we will deal with efficiency.

Definition 3.3 (Quantum Fourier Transform (QFT)). The quantum Fourier transform F_{N} is the operator on a register with n ≥ log N qubits given by

F_{N} = \frac{1}{\sqrt{N}} ∑_{j,k=0}^{N−1} e^{\frac{2πijk}{N}} |k⟩⟨j| (20)

Note later we will define the QFT over other groups, so this one is actually the cyclic QFT.

The \frac{1}{\sqrt{N}} factor is required to make this a unitary transformation^{11}, so it is a valid quantum transformation. Map the group, which we view as integers added modN, into the basis of the quantum state, that is, G = {|0⟩, |1⟩, …, |N − 1⟩} and H = {|0⟩, |d⟩, |2d⟩, …, |(M − 1)d⟩}. Compute on two registers:

7Private comment.

8Lomont [87] has shown that there can be no quantum correlation or convolution algorithms that parallel the quantum Fourier transform.

9Recall |x⟩|y⟩ merely means |x⟩ ⊗ |y⟩ and is used as shorthand.

10Check this is unitary, thus an allowable quantum operation.

11Homework!

(21)  |0⟩|0⟩ ⟶^{F_{N} on 1st} \frac{1}{\sqrt{N}} ∑_{j=0}^{N−1} |j⟩|0⟩

(22)  ⟶^{apply f}  \frac{1}{\sqrt{N}} ∑_{j=0}^{N−1} |j⟩|f(j)⟩

Measuring the second register to obtain some value f(j_{0}) collapses the state, leaving only those values in the first register that have f(j_{0}) in the second register, namely the coset H + j_{0}. This is where we needed that f separates cosets of H. This “entanglement” is not present in classical computation, and seems to be one source of the increased computational power of quantum computing, another source being the ability to do computations on 2^{n} state coefficients in parallel by manipulating only n qubits. We now drop the second register which remains |f(j_{0})⟩.

(23)  ⟶^{measure} \frac{1}{\sqrt{M}} ∑_{h∈H} |j_{0} + h⟩

(24)  =  \frac{1}{\sqrt{M}} ∑_{s=0}^{M−1} |j_{0} + sd⟩

(25)  ⟶^{apply F_{N}}  \frac{1}{\sqrt{M}} ∑_{s} \frac{1}{\sqrt{N}} ∑_{k=0}^{N−1} e^{\frac{2πi(j_{0}+sd)k}{N}} |k⟩

(26)  =  \frac{1}{\sqrt{MN}} ∑_{k=0}^{N−1} e^{\frac{2πij_{0}k}{N}} |k⟩ ∑_{s=0}^{M−1} e^{\frac{2πisdk}{N}}

Using \frac{d}{N} = M, evaluate the geometric series

(27)  ∑_{s=0}^{M−1} e^{\frac{2πisdk}{N}} = ∑_{s=0}^{M−1} (e^{\frac{2πik}{M}} )^{s}

(28)  = \{ \begin{matrix}0 & if M ∤ k \\ M & if M | k \end{matrix}

So in expression 26, only those values of k that are multiples of M remain, simplifying to the superposition

(29)  |ψ_{f}⟩ = \frac{1}{\sqrt{d}} ∑_{t=0}^{d−1} e^{\frac{2πij_{0}tM}{N}} |tM⟩

Now measuring at this point gives a multiple of M in {0, M, …, (d − 1)M} with uniform probability. All that remains is to repeat this to get several multiples of M, and to take the GCD to obtain M with high probability. Computing the GCD with the Euclidean algorithm^{12} has complexity O(log^{2} |N|), where log |N| is the number of digits in N.

To estimate how many trials we need, suppose we have obtained k multiples of M, say the (possibly repeated) multiples t_{1}, …, t_{k} ∈ T = {0, 1, …, d−1}. We want to estimate the probability that gcd(t_{1}, t_{2}, …, t_{k}) = 1, which would guarantee we would obtain the true value of M, and hence determine H properly. By lemma E.3 in appendix E,

12This is the oldest known algorithm [79].

prob (gcd(t_{1}, t_{2}, …, t_{k}) = 1) ≥ 1 − (\frac{1}{2})^{k/2}

Thus a few runs of the algorithm determines H with high probability, for any size N and d. To understand the complete cost of the algorithm, we need the computational cost of the QFT, which is shown next in section 3.4. Then we show how these pieces can be used to find hidden subgroups in any finite abelian group in section 3.5, and finally in section 3.6 we show some applications.

Above we assume infinitely precise values in the operations making the QFT. Since this is not physically reasonable, work has been done to cover the case of slight errors in the precision of the computations. Kitaev [77] and the error correction methods of Calderbank and Shor [27] are good places to start, and show that it is still possible to sample multiples of M with high probability even with errors in the QFT, so the process works.

3.4. Computing the Fourier Transform on ℤ_{N} Efficiently. In this section we want to show how to compute the quantum Fourier transform F_{N} on the cyclic group ℤ_{N} efficiently, or at least approximate it to as high a precision as necessary. We will do this in two steps: first we do it for the case N = 2^{n}, and then use this in the second step to do it for general N. F_{N} will be used to construct HSP algorithms for general finite abelian groups. We make the next definition for general groups, but reserve the more general QFT definition until section 4.3.

Definition 3.4. A family of quantum circuits {U_{i}} computing the quantum Fourier transform over a family of finite groups {G_{i}} is called efficient if U_{i} has size polynomial in log |G_{i}| for all i.

Efficient quantum circuits for the Fourier transform over ℤ_{N} are well studied. Kitaev [77] gives an approximate method. Mosca and Zalka [100] use “amplitude amplification” [25] to give an exact method, but claim it is unlikely to be of practical use. Mosca’s [98] thesis and Hales’ thesis [55] both contain circuit descriptions. Hales and Hallgren [57] give the algorithm used in appendix A for the general case. For practical implementations of Shor’s algorithm the “semiclassical” version given by Griffiths and Niu [52] would probably be the best known choice. Cleve and Watrous [33] have given parallel algorithms, showing even more speed increases. Shor [114] did the cyclic case for “smooth” values of N, and Coppersmith [35] gave an efficient algorithm for the case N = 2^{n} as well as an approximate version. Brassard and Høyer [23] show how to solve Simon’s problem, and have a useful framework for analyzing the general finite abelian HSP.

It has been said [59] that “The efficient algorithm for the abelian HSP is folklore.” This section attempts to clear that up with precision.

3.4.1. Reduction to Odd Order and 2^{n} Order. As mentioned in Mosca’s thesis [98, Appendix A.4], it is a fact that the Fourier transform F_{N} over a composite N = AB, with (A, B) = 1, can be computed efficiently from the efficient Fourier transforms over A and B. We show this briefly.

We assume (A, B) = 1, and we have efficient QFT algorithms for F_{A} and F_{B}. Let U_{B} be the unitary transform |x mod A⟩ ⟶^{U_{B}} |xB mod A⟩, and similarly |y mod B⟩ ⟶^{U_{A}} |yA mod B⟩. Both U_{A} and U_{B} are efficiently computable, since they are just multiplication, followed by a remainder operation.

The main idea comes from the ring isomorphism ℤ_{N} ≅ ℤ_{A} × ℤ_{B}, given in one direction by j → (j mod A, j mod B), and in the other direction by (j_{1}, j_{2}) → j_{1}BB^{−1} + j_{2}AA^{−1}, where AA^{−1} ≡ 1 mod B and BB^{−1} ≡ 1 mod A. These statements required (A, B) = 1. With this notation it is instructive to check

(30)  F_{N} = (U_{B} ⊗ U_{A}) (F_{A} ⊗ F_{B}) .

This reduces the general QFT over ℤ_{N} for general N to the cases N = 2^{n} and N odd. Finding QFT algorithms with time complexity of O(poly log N) for each case thus results in such an algorithm for any N, since U_{A} and U_{B} are efficient.

Thus for our purposes it is enough to show how to compute F_{N} efficiently for N a power of two and for N odd.

3.4.2. The Case N = 2^{n}. We start with the easiest case: N = 2^{n}. We show an explicit construction of the Fourier transform F_{N}, where N = 2^{n}. This presentation follows [29, Ch. 5], which in turn is adapted from sources mentioned in their book.

We use the notation from section 3.3, specialized to the case N = 2^{n}. We write the integer j in binary as j = j_{1}2^{n−1} + j_{2}2^{n−2} + ⋯ + j_{n}2^{0}, or in shorthand, as j = j_{1}j_{2} … j_{n}. We also adopt the notation 0.j_{l}j_{l−1} … j_{m} = j_{l}/2 + j_{l+1}/4 + ⋯ + j_{m}/2^{m−l+1}. Note the Fourier^{13} operator F_{N} sends a basis element |j⟩ to \frac{1}{\sqrt{N}} ∑_{k=0}^{N−1} ω_{N}^{jk}|k⟩. The inverse transform has ω_{N}^{−1} instead of ω_{N}. Then we can derive a formula giving an efficient way to compute the Fourier transform:

(31) F_{N}|j⟩ = \frac{1}{\sqrt{N}} ∑_{k=0}^{2^{n}−1} e^{\frac{2πijk}{2^{n}}} |k⟩

(32)  = \frac{1}{\sqrt{N}} ∑_{k_{1}=0}^{1} ∑_{k_{2}=0}^{1} ⋯ ∑_{k_{n}=0}^{1} e^{2πij ∑_{l=1}^{n} k_{l}2^{−l}}|k_{1}k_{2} … k_{n}⟩

(33)  = \frac{1}{\sqrt{N}} ∑_{k_{1}=0}^{1} ∑_{k_{2}=0}^{1} ⋯ ∑_{k_{n}=0}^{1} ⨂_{l=1}^{n} e^{2πijk_{l}2^{−l}}|k_{l}⟩

(34)  = \frac{1}{\sqrt{N}} ⨂_{l=1}^{n} [ ∑_{k_{l}=0}^{1} e^{2πijk_{l}2^{−l}}|k_{l}⟩]

(35)  = \frac{1}{\sqrt{N}} ⨂_{l=1}^{n} [|0⟩ + e^{2πij2^{−l}}|1⟩]

(36)  = \begin{matrix}(|0⟩ + e^{2πi0.j_{n}}|1⟩) & (|0⟩ + e^{2πi0.j_{n−1}j_{n}}|1⟩) & … & (|0⟩ + e^{2πi0.j_{1}j_{2}...j_{n}}|1⟩) \\ √ & \overline{N} \end{matrix}

where in the last step we used exp (2πij2^{−l}) = exp (2πij_{0}j_{1} … j_{n−l}.j_{n−l+1} … j_{n}) = exp (2πi0.j_{n−l+1} … j_{n}). Using this expression, we exhibit a quantum circuit (unitary operator) using O((log N)^{2}) elementary operations that transforms the state |j⟩ into the one shown in equation 36.

13Note that the Fourier coefficients can be viewed as group homomorphisms ω_{N}^{k} : ℤ_{N} → ℂ^{∗}, taking a → ω_{N}^{ka}. This viewpoint generalizes well.

We need two types of unitary^{14} operations, H^{(a)} and R_{k}^{(a,b)}, where a and b index

the qubits in the quantum machine, as follows^{15}: Let H^{(a)} = \frac{1}{\sqrt{2}} (\begin{matrix}1 & 1 \\ 1 & −1 \end{matrix}) be the

standard Hadamard operator, applied to qubit a, and let R_{k}^{(a,b)} be the operator on qubits a and b given by

R_{k}^{(a,b)} = (\begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & ω_{2^{k}} \end{matrix} )

where ω_{N} = e^{\frac{2πi}{N}} is the standard primitive N^{th} root of unity. R_{k}^{(a,b)} has the effect of multiplying the phase of the |1⟩ component of qubit b by ω_{2^{k}} if and only if qubit a is |1⟩, and is called a controlled phase change. For example, looking at the two-qubit state,

(37)  (α|0⟩ + β|1⟩) |1⟩ ⟶^{R_{5}^{(2,1)}}  (α|0⟩ + βe^{2πi/2^{5}}|1⟩) |1⟩

Note each H^{(a)} and R_{k}^{(a,b)} is a local interaction on the quantum state, so we will count the number of them needed to implement a Fourier transform.

Apply to the state |j_{1}j_{2} … j_{n}⟩ the operator R_{n}^{(n,1)}R_{n−1}^{(n−1,1)} … R_{2}^{(2,1)}H^{(1)}. We have

(38)  |j_{1}j_{2} … j_{n}⟩ ⟶^{H^{(1)}}  \frac{1}{\sqrt{2}} (|0⟩ + e^{2πi0.j_{1}}|1⟩) |j_{2}j_{3} … j_{n}⟩
(39)  ⟶^{R_{2}^{(2,1)}}  \frac{1}{\sqrt{2}} (|0⟩ + e^{2πi0.j_{1}j_{2}}|1⟩) |j_{2}j_{3} … j_{n}⟩

… (40)

(41)  ⟶^{R_{2}^{(n,1)}}  \frac{1}{\sqrt{2}} (|0⟩ + e^{2πi0.j_{1}j_{2}...j_{n}}|1⟩) |j_{2}j_{3} … j_{n}⟩

This required n local operations.

Apply to the state |j_{2}j_{3} … j_{n}⟩ the operator R_{n}^{(n,2)}R_{n−1}^{(n−1,2)} … R_{2}^{(3,2)}H^{(2)}, which changes only the second qubit, resulting similarly in

(42)  \frac{1}{\sqrt{2}} (|0⟩ + e^{2πi0.j_{1}j_{2}...j_{n}}|1⟩) \frac{1}{\sqrt{2}} (|0⟩ + e^{2πi0.j_{2}...j_{n}}|1⟩) |j_{3}j_{4} … j_{n}⟩

which required n−1 operations. Repeating this process uses 1+2+⋯+n = \frac{n(n+1)}{2} local operations and results in the state

(43)  \begin{matrix}(|0⟩ + e^{2πi0.j_{1}j_{2}...j_{n}}|1⟩) & \frac{1}{\sqrt{2}} & (|0⟩ + e^{2πi0.j_{2}...j_{n}}|1⟩) & … & (|0⟩ + e^{2πi0.j_{n}}|1⟩) \\ √ & \overline{N} \end{matrix}

Noting this is similar to equation 36, we finish the Fourier transform by reversing the order of the qubits with approximately ⌊\frac{n}{2}⌋ unitary qubit swaps. Thus the total number of operations, each affecting at most 2 qubits, is O(n^{2}) = O(log^{2} N). We get an exact F_{N} transform with this method.

14A careful reader should check these are unitary.

15Note Chuang and Nielsen in [29] denote R_{k} as a single qubit operator, ours is what they would call a controlled R_{k}.

Most discussions avoid the following point. Notice as N grows, so the number of basic operations R_{k} grows as log N, and this seems like cheating. If for each N = 2^{n} we use only H and R_{n}, we may construct R_{m}, 0 ≤ m ≤ n as (R_{n})^{(n−m)}, thus upping the complexity to O(log^{3} N), which seems more fair from a complexity standpoint. Also, the H^{(a)} were in list of elementary operations from section 2.2, but the R_{k}^{(a,b)} were not. We remark they can be approximated in a manner leaving the overall QFT circuit efficient.

So this shows how to get an exact transform in O(log^{2} N) or O(log^{3} N) operations, depending on one’s viewpoint. Since physical realizations will have error, we would be fine just approximating the QFT, a viewpoint detailed in Coppersmith [35], where he shows how to approximate the transform within any ϵ > 0 in time O(log N(log log N + log 1/ϵ)). See appendix A for more information on this result.

3.4.3. The Case N Odd. We use the algorithm over powers of 2 to get one for an odd N. The details of the proof are lengthy, and are left to Appendix A. The main result however gives

Theorem A.17. Given an odd integer N ≥ 13, and any \sqrt{2} ≥ ϵ > 0. Then F_{N} can be computed with error bounded by ϵ using at most ⌈12.53 + 3 log \frac{\sqrt{N}}{ϵ} ⌉ qubits. The algorithm has operation complexity

(44)  O (log \frac{\sqrt{N}}{ϵ} (log log \frac{\sqrt{N}}{ϵ} + log 1/ϵ))

The induced probability distributions D_{v} from the output and D from F_{N}|u⟩⊗|ψ⟩ satisfy

(45)  |D_{v} − D| ≤ 2ϵ + ϵ^{2}

This says we can approximate the QFT very well. For odd N < 13 we can also design circuits using the methods in the proof. It is not currently known how to construct an exact QFT for odd cyclic groups, so this is as good as it (currently) gets.

3.4.4. Final result: the Cyclic HSP Algorithm. Combining sections 3.4.2 and 3.4.3 with the reasoning in section 3.3, we end up with the cyclic HSP algorithm:

The Hidden Subgroup Algorithm, Cyclic Abelian Case

Given: The group G = ℤ_{N} for a positive integer N, and a quantum blackbox that evaluates a function f : |x⟩|y⟩ → |x⟩|f(x) ⊕ y⟩, which we assume requires constant time^{16}.

Promise: f is constant on a subgroup H = ⟨d⟩ of G, and is distinct on cosets

of H. Output: The integer d, in time O(log^{2} N) with probability at least \frac{3}{4}, and

using at most O(poly(log N)) qubits.

We proceed as follows

(1) Do the following steps for 8 trials, obtaining samples t_{1}, t_{2}, ..., t_{8}.

(a) On the initial state |0⟩|0⟩ apply the quantum Fourier transform F_{N} (as earlier), with an approximation error of at most ϵ = 0.01.

16Even if the time to compute f is not constant, if f can be computed efficiently, the overall algorithm is still efficient since f is called only a few times.

(b) Apply f in constant time.

(c) Sample the registers in constant time, obtaining t_{j}, a multiple of M =

|H|.

(2) Compute M = gcd(t_{1}, t_{2}, …, t_{8}) using the Euclidean algorithm^{17} in time O(log^{2} N).

(3) Output the answer d = N/M.

The probability of any one run returning a valid sample is at least 1 − (2ϵ + ϵ^{2}). We fix ϵ = 0.01. We require 8 good samples, at which point the probability of them returning the correct GCD is at least 1 − (1/2)^{4}, so the probability of success is then (1 − (.0201))^{8}(15/16) > 3/4. Oddly enough, the Euclidean Algorithm to compute the GCD requires more time than the QFT, and the result follows.

3.5. The General Finite Abelian Group. We want to generalize the cyclic case algorithm to all finite abelian groups. This discussion is a mixture of [23] and [36], with unified notation, and minor changes and corrections.

A basic result about finite abelian groups is the following structure theorem (Lang [83]):

Theorem 3.5. Every finite abelian group G is a direct sum of cyclic groups.

That is, G ≅ ℤ_{N_{1}} ⊕ ℤ_{N_{2}} ⊕ … ℤ_{N_{k}}. Given generators for G, finding the N_{i} is hard classically, but Cheung and Mosca [28] (Theorem 5.23 below) give an efficient quantum algorithm to find the N_{i}. For example, given the cyclic group ℤ_{N}, there is no known efficient classical algorithm to find the decomposition of the multiplicative group ℤ_{N}^{∗} of integers relatively prime to N. Yet classically we can compute within this group efficiently.

So from now on, we assume we know the decomposition of our finite abelian group G, and can compute in G efficiently both classically (and hence) quantum mechanically.

Let G = ℤ_{N_{1}} ⊕ ⋯ ⊕ ℤ_{N_{k}} be a finite additive abelian group, and assume we have a function f from G to a finite set X, such that there is a subgroup H < G such that f separates cosets of H as in section 3.1. Denote elements of G as ktuples: g = (g_{1}, …, g_{k}), where we view g_{j} either as an integer mod N_{j} or an integer ∈ {0, 1, …, N_{j} − 1}. Write −g for the (additive) inverse of g ∈ G.

To generalize the cyclic group Fourier transform F_{N} to an arbitrary finite abelian group, we need some representation theory, specifically character theory, and to this area we now turn. See also section 4.2 for representation theory basics.

3.5.1. Character Theory of Finite Abelian Groups. To define a Fourier transform over G, we need to generalize the ω_{N}^{jk} terms from the cyclic case, basically by putting one such term for each entry in the k-tuple description of G.

Definition 3.6. A character of a group G is a group homomorphism from G to the multiplicative group of nonzero complex numbers ℂ^{∗}.

Recall this is then just a map of sets χ : G → ℂ^{∗} such that

(46)  χ(g_{1} + g_{2}) = χ(g_{1})χ(g_{2})

17The GCD complexity follows from O(log N) time algorithms for division in [15] and that the most steps used in the Euclidean algorithm happens when the input is two consecutive Fibonacci numbers multiplied by an integer.

We think of G as having an additive structure, and ℂ^{∗} a multiplicative structure. From this simple definition we derive some tools and facts which will allow us to finish the HSP discussion for finite abelian groups.

Our first task is to describe all characters χ : G → ℂ^{∗}. Denote the identity of G by e = (0, 0, …, 0); the identity of ℂ^{∗} is 1.

Let χ : G → ℂ^{∗} be a character (so χ(ng) = χ(g)^{n} for any integer n and group element g). Let β_{1} = (1, 0, 0, …, 0) ∈ G, β_{2} = (0, 1, 0, 0 …, 0) ∈ G, …, β_{k} = (0, 0, …, 0, 1) ∈ G. Then for any element g = (g_{1}, g_{2}, …, g_{k}) we have

(47)  χ(g) = χ (∑_{j=1}^{k} g_{j}β_{j})

(48)  = ∏_{j=1}^{k} χ(β_{j})^{g_{j}}

so χ is completely determined by its values on the β_{j}. Since β_{j} has order N_{j}, χ(β_{j}) must have order dividing N_{j}, for each j. Then we must have^{18} that χ(β_{j}) = ω_{N_{j}}^{h_{j}} for some integer h_{j}. It is sufficient to consider h_{j} ∈ {0, 1, …, N_{j} − 1} since the values of ω_{N_{j}}^{h_{j}} are periodic, so any given character χ : G → ℂ^{∗} is determined by a k-tuple (h_{1}, h_{2}, …, h_{k}), which may be viewed as an element h ∈ G. This allows labelling each distinct character χ by an element of G: for each g ∈ G define the character χ_{g} : G → ℂ^{∗} via χ_{g}(h) = ∏_{j=1}^{k} ω_{N_{j}}^{g_{j}h_{j}}, for h ∈ G. From this definition we notice that for all g, h ∈ G

(49)  χ_{g}(h) = χ_{h}(g)
(50)  χ_{g}(−h) = \frac{1}{χ_{g}(h)}

Let χ(G) denote the set of all such homomorphisms, which is a group under the operation χ_{g_{1}}χ_{g_{2}} = χ_{g_{1}+g_{2}} with identity χ_{e}. Then we prove

Theorem 3.7. For a finite abelian group G, χ(G) ≅ G.

Proof. From the discussion above, there is a set bijection between the two sets given (in one direction) by α : g → χ_{g}, which is also a group isomorphism. The identity e = (0, 0, …, 0) ∈ G is sent to the identity α(e) = χ_{e} in χ(G), and α(g_{1} + g_{2}) = χ_{g_{1}+g_{2}} = χ_{g_{1}}χ_{g_{2}} = α(g_{1})α(g_{2}), making α a group homomorphism and a set bijection, thus an isomorphism. □

In the cyclic QFT algorithm, we sampled elements that were multiples of the generator of the subgroup H, and to generalize this to the finite abelian case where there may not be a single generator, we introduce orthogonal elements. For any subset X ⊆ G, we say an element h ∈ G is orthogonal to X if χ_{h}(x) = 1 for all x ∈ X. Then for any subgroup H < G we define the orthogonal subgroup

H^{⊥} = {g ∈ G|χ_{g}(h) = 1 for all h ∈ H} (51)

as the set of all elements in G orthogonal to H. H^{⊥} is a subgroup of G as follows: the identity e ∈ G is in H⊥ since χ_{e}(g) = 1 for all g ∈ G, and if a, b ∈ H^{⊥} then for any h ∈ H we have χ_{h}(a − b) = χ_{h}(a)/χ_{h}(b) = 1 so a − b ∈ H^{⊥}, and H^{⊥} is a subgroup of G.

18Recall ω_{N} is a primitive N^{th} root of unity, from section 1.3.

Note 3.8. These orthogonal subgroups are not quite like orthogonal subspaces. For example, we could have nontrivial H ∩ H^{⊥}, unlike the vector space example. Here is an example following [36] where H = H^{⊥} ≠ G. Let G = ℤ_{4}, H = {0, 2}. Then H^{⊥} = {(a) ∈ G|(i)^{ah} = 1 for all (h) ∈ H} = {(a)|(−1)^{a} = 1} = H. This can be extended to give examples of varying weirdness.

Another useful fact is

Theorem 3.9. Let G be a finite abelian group, and χ ∈ χ(G) a fixed character, and χ_{e} the identity character sending G → 1. Then

(52)  ∑_{g∈G} χ(g) = \{ \begin{matrix}|G| & if χ = χ_{e} \\ 0 & if χ ≠ χ_{e} \end{matrix}

Proof. Fix G ≅ ℤ_{N_{1}} ⊕ ⋯ ⊕ ℤ_{N_{k}}, and by theorem 3.7 fix h ∈ G with χ = χ_{h}. Using the notation above,

(53) ∑_{g∈G} χ_{h}(g) = ∑_{g_{1}∈ℤ_{N_{1}}} ∑_{g_{2}∈ℤ_{N_{2}}} ⋯ ∑_{g_{k}∈ℤ_{N_{k}}} ∏_{j=1}^{k} ω_{N_{j}}^{h_{j}g_{j}}

(54)  = ( ∑_{g_{1}∈ℤ_{N_{1}}} ω_{N_{1}}^{h_{1}g_{1}} ) ( ∑_{g_{2}∈ℤ_{N_{2}}} ω_{N_{2}}^{h_{2}g_{2}} ) … ( ∑_{g_{k}∈ℤ_{N_{k}}} ω_{N_{k}}^{h_{k}g_{k}} )

If some ω_{N_{j}}^{h_{j}} ≠ 1, then the geometric series ∑_{g_{j}∈ℤ_{N_{j}}} (ω_{N_{j}}^{h_{j}})^{g_{j}} = 0, making the entire product 0. This happens if and only if χ_{h} ≠ χ_{e}. If χ_{h} = χ_{e} then the sum is |G|. □

We now prove some relations between H and H^{⊥}.

Theorem 3.10. With the notation above,

(55)  G/H ≅ H^{⊥}
(56)  H^{⊥⊥} = H

Proof. Using theorem 3.7, we already have H^{⊥} ≅ χ(H^{⊥}) and χ(G/H) ≅ G/H, so it is enough to prove χ(H^{⊥}) ≅ χ(G/H). For any element g ∈ G let \overline{g} denote the image in G/H under the projection map π : G → G/H. Note that any character χ_{h′} ∈ χ(H^{⊥}) coming from an element h′ ∈ H^{⊥} can also be viewed as a character on G, since h′ is also in G. Then define a map α : χ(H^{⊥}) → χ(G/H) via

(αχ) (\overline{g}) = χ_{h′}(g)

where \overline{g} ∈ G/H and g is any coset representative, i.e., \overline{g} = g + H. We will show α is a group isomorphism.

α is well defined since if g_{1} and g_{2} are different representations of the same coset \overline{g_{1}} = \overline{g_{2}}, then there is an h ∈ H with g_{1} − g_{2} = h, giving (αχ_{h′})(\overline{g_{1}}) = χ_{h′}(g_{1}) ∗ 1 = χ_{h′}(g_{1} + h) = χ_{h′}(g_{2}) = (αχ_{h′})(\overline{g_{2}}). For the identity χ_{e} ∈ χ(H^{⊥}) and any \overline{g} ∈ G/H we have (αχ_{e})(\overline{g}) = χ_{e}(g) = 1, so αχ_{e} is the identity in χ(G/H). Also for \overline{(}g) ∈ G (α(χ_{h_{1}}χ_{h_{2}}))(\overline{g}) = (α(χ_{h_{1}+h_{2}}))(\overline{g}) = χ_{h_{1}+h_{2}}(g) = χ_{h_{1}}(g)χ_{h_{2}}(g) = ((αχ_{h_{1}})(αχ_{h_{2}}))(\overline{g}), so α is a group homomorphism.

To show α is injective, suppose for some h′ ∈ H^{⊥} that αχ_{h′} is the identity in χ(G/H). Take any g ∈ G. αχ_{h′}(\overline{g}) = 1 implies χ_{h′}(g) = 1, and since this is for any g ∈ G, we have χ_{h′} = χ_{e}. G ≅ χ(G) then gives h′ = e, and thus α is injective.

Now all we need is to show alpha is surjective. Let \overline{χ} ∈ χG/H. The composite map with the projection π : G → G/H gives a homomorphism χ = \overline{χ} ∘ π : G ⟶^{π} G/H ⟶^{\overline{χ}} ℂ^{∗}, thus is a character, say χ_{t}, for some fixed t ∈ G. For h ∈ H this evaluates to χ_{t}(h) = \overline{χ}(\overline{e}) = 1, so t ∈ H^{⊥}, and χ_{t} ∈ χ(H^{⊥}). To show αχ_{t} = \overline{χ}, let \overline{g} ∈ G/H, and compute: (αχ_{t})(\overline{g}) = χ_{t}(g) = \overline{χ}π(g) = \overline{χ}(\overline{g}). Thus α is surjective and thus a group isomorphism.

To show H^{⊥⊥} = H start with the isomorphism already proven: |G/H| = |H^{⊥}| gives |G/H^{⊥}| = |H| and also implies |G/H^{⊥}| = |H^{⊥⊥}|, giving |H| = |H^{⊥⊥}|. Fix h ∈ H. By definition H^{⊥⊥} = {g ∈ G|χ_{g}(h′) = 1 for all h′ ∈ H^{⊥}}. In particular χ_{h}(h′) = χ_{h′}(h) = 1 for all h′ ∈ H^{⊥} by the definition of H^{⊥}, so we have h ∈ H^{⊥⊥}, giving H ⊆ H^{⊥⊥}. Thus H = H^{⊥⊥}. □

3.5.2. The General Finite Abelian Group Quantum Fourier Transform. We continue the notation from the previous section. Similar to the cyclic QFT algorithm returning multiples of the generator of H (which is really the orthogonal subgroup), this general finite abelian QFT algorithm will return elements of the orthogonal subgroup H^{⊥}. We start with the Fourier transform.

We define three quantum operators over the group G: the Fourier transform F_{G} over G, the translation operator τ_{t} for a t ∈ G, and the phase-change operator ϕ_{h} for h ∈ G as

(57)  F_{G} = \frac{1}{\sqrt{|G|}} ∑_{g,h∈G} χ_{g}(h)|g⟩⟨h|
(58)  τ_{t} = ∑_{g∈G} |t + g⟩⟨g|
(59)  ϕ_{h} = ∑_{g∈G} χ_{g}(h)|g⟩⟨g|

Note that for cyclic G = ℤ_{N} the Fourier transform is the same as earlier in section 3.3, since then χ_{h}(g) = e^{\frac{2πihg}{N}}, and we recover the earlier algorithm.

First we check that the Fourier transform maps a subgroup H to its orthogonal subgroup H^{⊥}.

Theorem 3.11.

(60)  F_{G}|H⟩ = |H^{⊥}⟩

Proof. Recall from the definition of a subset |H⟩ = \frac{1}{\sqrt{|H|}} ∑_{h∈H} |h⟩. Then

(61)  F_{G}|H⟩ = \frac{1}{\sqrt{|G|}} ∑_{g,h′∈G} χ_{g}(h′)|g⟩⟨h′|\frac{1}{\sqrt{|H|}} ∑_{h∈H} |h⟩

(62)  = \frac{1}{\sqrt{|G||H|}} ∑_{\begin{matrix}g,h′∈G \\ h∈H \end{matrix}} χ_{g}(h′)|g⟩⟨h′|h⟩

(63)  = \frac{1}{\sqrt{|G||H|}} ∑_{\begin{matrix}g∈G \\ h∈H \end{matrix}} χ_{g}(h)|g⟩

(64)  = \frac{1}{\sqrt{|G||H|}} ∑_{g∈G} ( ∑_{h∈H} χ_{g}(h)) |g⟩

Now consider the coefficient ∑_{h∈H} χ_{g}(h) of the ket |g⟩. The G character χ_{g} is also a character of H, so by theorem 3.9 the sum is 0 unless the character is the identity on H, in which case the sum is |H|. χ_{g} is the identity on H precisely when χ_{g}(h) = 1 for all h ∈ H, i.e., g ∈ H^{⊥}. So equation 64 becomes

(65)  \frac{1}{\sqrt{|G||H|}} ∑_{g∈H^{⊥}} |H||g⟩ = \sqrt{\frac{|H|}{|G|}} ∑_{g∈H^{⊥}} |g⟩
(66)  = |H^{⊥}⟩

where we used theorem 3.10 to get \frac{|H|}{|G|} = \frac{1}{|H^{⊥}|}. □

We also have

Theorem 3.12 (Commutative laws of the G-operators). For every h, t ∈ G we have

(67)  χ_{h}(t)τ_{t}ϕ_{h} = ϕ_{h}τ_{t}
(68)  F_{G}ϕ_{h} = τ_{−h}F_{G}
(69)  F_{G}τ_{t} = ϕ_{t}F_{G}

Proof. We prove the last one, which is the only one we explicitly use. The rest are similar. We use the identity I = ∑_{g∈G} |g⟩⟨g|.

F_{G}τ_{t} = (\frac{1}{\sqrt{|G|}} ∑_{g,h∈G} χ_{g}(h)|g⟩⟨h|) ( ∑_{g′∈G} |t + g′⟩⟨g′|)

= \frac{1}{\sqrt{|G|}} ∑_{g,g′,h∈G} χ_{g}(h)|g⟩⟨h|t + g′⟩⟨g′|

= \frac{1}{\sqrt{|G|}} ∑_{g,g′∈G} χ_{g}(t + g′)|g⟩⟨g′|

= \frac{1}{\sqrt{|G|}} ∑_{g,g′∈G} χ_{g}(t)χ_{g}(g′)|g⟩⟨g′|

= \frac{1}{\sqrt{|G|}} ∑_{a,g,g′∈G} χ_{g}(t)χ_{g}(g′)|a⟩⟨a|g⟩⟨g′|

= \frac{1}{\sqrt{|G|}} ∑_{a,g,g′∈G} χ_{a}(t)χ_{g}(g′)|a⟩⟨a|g⟩⟨g′|

= (∑_{a∈G} χ_{a}(t)|a⟩⟨a|) (\frac{1}{\sqrt{|G|}} ∑_{g,g′∈G} χ_{g}(g′)|g⟩⟨g′|)
= ϕ_{t}F_{G}
□

Then the algorithm becomes:

(1) Apply the quantum Fourier transform^{19} to the first register of the zero state on two registers:

|0⟩|0⟩ ⟶^{F_{G}} \frac{1}{\sqrt{|G|}} ∑_{g∈G} |g⟩|0⟩

obtaining a superposition over all elements of G.

(2) Apply the coset separating function f:

⟶^{f} \frac{1}{\sqrt{|G|}} ∑_{g∈G} |g⟩|f(g)⟩

and as before, f constant and distinct on cosets allows the simplification

= \frac{1}{\sqrt{|T |}} ∑_{t∈T} |t + H⟩|f(t)⟩

= \frac{1}{\sqrt{|T |}} ∑_{t∈T} τ_{t}|H⟩|f(t)⟩

where T = {t_{1}, …, t_{m}} is a transversal (set of coset representatives) for H in G.

(3) Apply the Fourier transform F_{G} to the first register, and apply theorems 3.11 and 3.12

⟶^{F_{G}}  \frac{1}{\sqrt{|T |}} ∑_{t∈T} F_{G}τ_{t}|H⟩|f(t)⟩

= \frac{1}{\sqrt{|T |}} ∑_{t∈T} ϕ_{t}F_{G}|H⟩|f(t)⟩

= \frac{1}{\sqrt{|H^{⊥}|}} ∑_{t∈T} ϕ_{t}|H^{⊥}⟩|f(t)⟩

We used that |T | = |G|/|H| = |H^{⊥}| by theorem 3.10. Note we could have measured the second register as in the cyclic case, but a fact called “The Principle of Deferred Measurement” allows us to measure at the end^{20}.

(4) Measure the first register, obtaining a random element (uniformly distributed) of H^{⊥}. Note that the phase ϕ_{t} does not affect amplitudes, so we could measure the second register first if we desired, fixing a t_{0}, as mentioned in the previous step.

This algorithm returns uniformly distributed random elements of H^{⊥}. Since (H^{⊥})^{⊥} = H, determining a generating set for H^{⊥} determines H uniquely. The following discussion comes from [36], with details not mentioned there to make the results precise.

Theorem D.1 in appendix D proves that choosing t+⌈log |G|⌉ uniformly random elements of a finite group G will generate G with probability greater than 1 − \frac{1}{2^{t}}.

19Usually the inverse transform is applied here, but this has the same effect for the |0⟩ state.

[36, Lemma 8] allows quicker setting of these superposed states with high probability.

20As you will see we still get the desired outcome whether or not we measure twice, or only once at the end.

For the moment assume we have chosen a generating^{21} set g^{1}, g^{2}, …, g^{t} for H^{⊥}. We want to find efficiently a generating set for H, finishing the algorithm. Since H^{⊥⊥} = H, an element h ∈ H if and only if χ_{h}(h′_{j}) = 1 for all j = 1, 2, …, t. Next we make these relations linear.

Let d = LCM{N_{1}, N_{2}, …, N_{k}}. Set α_{l} = d/N_{l}, giving ω_{N_{l}} = ω_{d}^{α_{l}}. Then

χ_{h}(g^{j}) = ∏_{l=1}^{k} ω_{d}^{α_{l}h_{l}g_{l}^{j}} = 1 if and only if ∑_{l=1}^{k} α_{l}h_{l}g_{l}^{j} ≡ 0 (mod d). So to find elements of H, we find random solutions to the system of t linear equations

(70)

α_{1}g_{1}^{1}X_{1} + α_{2}g_{2}^{1}X_{2} + ⋯ + α_{k}g_{k}^{1}X_{k} ≡ 0 (mod d)
α_{1}g_{1}^{2}X_{1} + α_{2}g_{2}^{2}X_{2} + ⋯ + α_{k}g_{k}^{2}X_{k} ≡ 0 (mod d)
⋮  ⋮
α_{1}g_{1}^{t}X_{1} + α_{2}g_{2}^{t}X_{2} + ⋯ + α_{k}g_{k}^{t}X_{k} ≡ 0 (mod d)

We do the following. Run the algorithm T = t_{1} +⌈log |G|⌉ times, giving elements g^{1}, g^{2}, …, g^{T} ∈ H^{⊥}. Since H^{⊥} ⊆ G, these elements generate H^{⊥} with probability p_{1} ≥ 1−1/2^{t_{1}}. We want to sample solutions to the system of equations 70 randomly and uniformly, to get S = t_{2} +⌈log |G|⌉ samples of H, which would generate H with probability p_{2} ≥ 1 − 1/2^{t_{2}}. To sample the solutions, view the equations in matrix form AX ≡ 0 (mod d), and then compute the Smith normal form^{22} of A, that is, a diagonal matrix D such that D = UAV with U and V being integer valued invertible matrices. Then we can uniformly randomly find solutions to DY ≡ 0 (mod d) by solving simple linear congruences, and then compute X = V Y, which is a uniformly randomly selected solution to the system of equations 70. This determines generators of H with probability at least (1 − \frac{1}{2^{t_{1}}} )(1 − \frac{1}{2^{t_{2}}} ).

Note that F_{G} = ⊗_{j=1}^{k}F_{N_{j}}, so we compute it by using the cyclic case algorithm from section 3.4.4, with the time complexity listed there. Choosing t_{1} = t_{2} = ⌈log |G|⌉ + 1 gives a probability of success at least 1 − \frac{1}{|G|}. After obtaining the system of equations 70, we compute D and V in time O(log |G| log log |G|) as in [120]. Then we sample the resulting system O(log |G|) times, and convert the answers to solutions to 70, totaling a time O(poly(log |G|)).

Thus we have proven the following (partially stated in Ettinger and Høyer [45], theorem 2.2.)

Theorem 3.13 (Finite abelian HSP algorithm). Given a finite abelian group G, a finite set X, and a function f : G → X that separates cosets of H for some subgroup H < G, then there exists a quantum algorithm that outputs a subset S ⊆ H such that S is a generating set for H with probability at least 1 − 1/|G|. The algorithm uses O(log |G|) evaluations of f, and runs in time polynomial in log |G| and in the time required to compute f, using a quantum circuit of size O(log |G| log log |G|).

3.6. The Standard Problems. Now that we can efficiently find hidden subgroups of finite abelian groups, we show a few examples of how to use the algorithms. For a longer list of examples, see [29, Figure 5.5]. We merely mention some algorithms that fall into this framework: Deutsch’s algorithm [37] (modified by Cleve), Deutsch and Jozsa’s algorithm [38], Simon’s algorithm [118], Shor’s factoring and discrete log algorithms [115], hidden linear function algorithms, and the abelian stabilizer algorithm [77]. Now on to two examples.

21Here the exponent does not denote power, but is used since later we will use subscripts on these elements.

22[120] shows how to compute the Smith Normal D = UAV form of an m×n integer matrix A mod d in time O(n^{2}m), and recover the U and V in time O(n^{2}m log^{c}(n^{2}m)), for some constant c > 0.

3.6.1. Simon’s Algorithm. Simon’s [118] algorithm distinguishes a trivial subgroup from an order 2 subgroup over the additive group ℤ_{2}^{n}. He showed that a classical probabilistic oracle requires exponentially many (in n) more oracle queries than a quantum algorithm to distinguish the two subgroup types with probability greater than 1/2, giving a major boost to the argument that quantum computers may be more powerful than classical ones. He posed the following problem in 1994 (modified somewhat to fit our discussion):

GIVEN a function f : ℤ_{2}^{n} → ℤ_{2}^{m} with m ≥ n, and such that there is a constant s ∈ ℤ_{2}^{n} for which f(x) = f(x′) if and only if x = x′ ⊕ s, where ⊕ is componentwise (binary) addition.

FIND s.

Here the subgroup is H = {0, s} < G = ℤ_{2}^{n}, and so we can find it quickly with high probability using the algorithm from theorem 3.13. However, to solve this classically, one may have to call f O(|G|) times, evaluating f on many points, to find the value s.

3.6.2. Shor’s Factoring Algorithm. Shor [114] generalizes Simon’s algorithm to obtain an integer factorization (and discrete log) algorithm. A good explanation is also in [69]. Integer factorization is classically very hard (see Lenstra and Pomerance [71]), and is the basis of the widely used public key cryptography algorithm RSA. Shor’s Integer Factorization Algorithm reduces to finding the order r of an integer x mod N, that is, the smallest r such that x^{r} ≡ 1 mod N. We wish to factor a composite integer N > 0, and it suffices to find a non-trivial solution to x^{2} ≡ 1 mod N, then x + 1 or x − 1 is a factor of N. A randomly chosen y relatively prime to N is likely to have even order, giving the solution x = y^{(r/2)}. All of this, except the order finding part, is efficient classically. Thus the hard part of the problem is to find the order of a given x modulo N. In other words, f(a) = x^{a} mod N, so f(a + r) = f(a) for all a, and the HSP finds the generator r of the subgroup ⟨r⟩ = H < G = ℤ_{N}.

3.7. Conclusion. In conclusion, we have shown that for any finite abelian group G, and any efficiently computable function f that separates cosets of some subgroup H < G, we can efficiently find a generating set for H with high probability. This was summarized in theorem 3.13.

In the process of doing this we isolated a few items needed to construct an efficient HSP algorithm for a group G:

(1) An efficient way is needed to compute the quantum Fourier transform over the group G. This evolved from the simple Fourier transform, through a more abstract one involving character theory, and in the general setting will involve representation theory^{23} to define the Fourier transform over nonabelian groups.

(2) An efficient way is needed to compute the coset separating function f. For Shor’s algorithm this is raising an integer to a power mod N, which is efficient classically. Simon’s algorithm had bitwise addition as the function, which also is efficient classically.

23See section 4.2 for representation theory basics.

(3) Finally, these HSP algorithms needed some post processing to extract the desired information from the randomly sampled elements of the orthogonal subgroup. This will turn out to be hard for nonabelian groups. Groups are known with efficient quantum Fourier transforms, but no known polynomial time algorithm is available to reconstruct hidden subgroups.

With that said, let’s begin analyzing the general (nonabelian case).

4. The General Hidden Subgroup Problem

Why do we want to find hidden subgroups of nonabelian groups? An efficient abelian HSP algorithm yielded an integer factoring algorithm which is exponentially faster than any known classical algorithm. Similarly, finding efficient HSP algorithms over certain nonabelian groups would yield algorithms faster than any known classical ones for several important problems, two of which we now explain.

4.1. Importance. One of the main reasons much research has been done into the HSP problem for nonabelian groups is the desire to find an efficient algorithm for the Graph Isomorphism problem: when are two graphs isomorphic? This algorithm has eluded researchers for over thirty years [81, 94]. Appendix B shows equivalences between several graph related algorithms, and describes several reductions. One reduction shown in appendix B gives that if the HSP could be solved efficiently for the symmetric group S_{n}, then we would have a polynomial time algorithm for the Graph Isomorphism Problem.

Another reason is that an efficient algorithm for solving the HSP for the dihedral group D_{n} would yield a fast algorithm for finding the shortest vector in a lattice, first shown by Regev [107]. This would yield another algorithm whose classical counterpart is much less efficient than the quantum version. Finding the shortest lattice vector has many uses, including applications to cryptography.

Before we cover the nonabelian HSP, we need to generalize the QFT algorithm, which is what the rest of this section will do. Then section 5 will list the main results known so far for the nonabelian HSP.

4.2. Representation Theory Overview. To generalize the abelian QFT algorithm, we need the nonabelian analogue of the Fourier transform. The method explained in section 3.5 shows the general machinery: we need representations of the group G. What follows is a brief overview of representation theory, which can be seen in detail in either of the excellent texts Fulton-Harris [63] or Serre [113]. We only cover enough of the definitions and facts to define precisely the quantum Fourier transform for finite groups. Some definitions and facts:

Representation. A representation ρ of a group G is a group homomorphism ρ : G → GL(V) where V is a vector space over a field 𝔽. For our purposes G will be finite, V will be finite dimensional of (varying) dimension d, and the field 𝔽 will be the complex numbers ℂ. Fixing a basis of V, each g ∈ G gives rise to a d × d invertible matrix ρ(g), which we can take to be unitary. The dimension d_{ρ} of the representation is the dimension d of V. We will often use the term irrep as shorthand for an irreducible representation.

We say two representations ρ_{1} : G → GL(V) and ρ_{2} : G → GL(W) are isomorphic when there is a linear vector space isomorphism ϕ : V ≅ W such that for all g ∈ G and v ∈ V, ρ_{1}(g)(v) = ρ_{2}(g)(ϕ(v)). In this case we write ρ_{1} ≅ ρ_{2}.

Irreducibility. We say a subspace W ⊆ V is an invariant subspace of a representation ρ if ρ(g)W ⊆ W for all g ∈ G. Thus the zero subspace and the total space V are invariant subspaces. If there are no nonzero proper subspaces, the representation is said to be irreducible.

Decomposition. When a representation does have a nonzero proper subspace V_{1} ⊊ V, it is always possible to find a complementary invariant subspace V_{2} so that V = V_{1} ⊕ V_{2}. The restriction of ρ to V_{i} is written ρ_{i}, and these give representations ρ_{i} : G → GL(V_{i}). Then ρ = ρ_{1} ⊕ ρ_{2}, and there is a basis of V so that each matrix ρ(g) is in block diagonal form with a block for each ρ_{i}.

Complete reducibility. Repeating the decomposition process, we obtain for any representation a decomposition ρ = ρ_{1} ⊕ ⋯ ⊕ ρ_{k}, where each representation ρ_{i} is irreducible. This is unique up to permutation of isomorphic factors.

Complete set of irreducibles. Given a group G, there are a finite number of irreducible representations up to isomorphism. We label this set Ĝ. Then we have the fact

(71)  |G| = ∑_{ρ∈Ĝ} d_{ρ}^{2}.

Characters. To a representation ρ is associated a character χ_{ρ} defined by χ_{ρ}(g) = tr(ρ(g)), where tr is the trace of the matrix. It is basis independent. An alternative, equivalent description is that a character is a group homomorphism χ : G → ℂ^{∗} where ℂ^{∗} denotes complex numbers of unit length, and the operation in C is multiplication, as we saw in section 3.5. Characters are fixed on conjugacy classes, which follows easily from the second definition: χ(hgh^{−1}) = χ(h)χ(g)χ(h^{−1}) = χ(g).

Orthogonality of characters. For two functions f_{1}, f_{2} : G → ℂ, there is a natural inner product ⟨f_{1}, f_{2}⟩_{G} = \frac{1}{|G|} ∑_{g∈G} f_{1}(g)f_{2}(g)^{∗} where ∗ denotes complex conjugation. The main fact is: given the character χ_{ρ} of a representation ρ and the character χ_{i} of an irreducible representation ρ_{i}, the inner product ⟨χ_{ρ}, χ_{i}⟩_{G} is exactly the number of times the representation ρ_{i} appears in the decomposition of ρ into irreducibles. Taking each ρ as unitary simplifies the inner product to

⟨χ_{ρ}, χ_{i}⟩_{G} = \frac{1}{|G|} ∑_{g∈G} χ_{ρ}(g)χ_{i}(g^{−1})

Orthogonality of the second kind. Let C be a conjugacy class of G. Since a character χ_{ρ} is fixed on a conjugacy class, let this value be χ_{ρ}(C). Then

∑_{ρ∈Ĝ} |χ_{ρ}(C)|^{2} = \frac{|G|}{|C|}

The Regular Representation. Take dim V = |G|, and fix a basis of V indexed by elements of G, labelling the basis as e_{g}. Then the regular representation ρ_{G} : G → GL(V) is defined by G permuting the basis elements, i.e., ρ_{G}(g)e_{x} = e_{gx}, extended ℂ-linearly. Thus the dimension of the regular representation is |G|. Another way to view this representation is as the group algebra ℂ[G].

The regular representation contains as subrepresentations every irreducible representation of G. If ρ_{1}, …, ρ_{k} are all the possible irreducible representations of G, then

ρ_{G} = ρ_{1}^{⊕d_{ρ_{1}}} ⊕ ⋯ ⊕ ρ_{k}^{⊕d_{ρ_{k}}}

that is, each irreducible ρ_{i} is contained exactly d_{ρ_{i}} times. This yields the important relation in equation 71. Taking the character associated to this gives, for g ∈ G, the “regular character”

(72)  χ_{G}(g) = ∑_{ρ∈Ĝ} d_{ρ}χ_{ρ}(g) = \begin{cases}0 if g ≠ e \\ N if g = e \end{cases} ,

where the last equality is obtained by noting that ρ(g) acts on ℂ[G] by permuting basis elements, so the trace is 0 if g ≠ e (all basis elements are permuted by any non-identity element g, so the diagonal is all 0’s) and is otherwise N.

The Induced Representation. Given a representation ρ : H → GL(W) of a subgroup H in a group G, we can define a way to extend this to a representation on G written Ind_{H}^{G}ρ : G → GL(V), unique up to isomorphism. The idea is to make copies of W for each coset of H in G, and let cosets permute the copies. So let Λ = {e, τ_{1}, …, τ_{k}} be a complete set of coset representatives, and let V = ⊕_{τ∈Λ}W_{τ}. Then any g ∈ G can be written g = τ_{g}h_{g} for some representative τ_{g} ∈ Λ and h_{g} ∈ H, which acts on V via τ_{g}h_{g} (⊕W_{τ}) = ⊕h_{g}W_{τ_{g}τ}.

For representation theory on various groups, most notably the symmetric group S_{n}, see James and Kerber [67], Kerber [75, 76], and Simon [117]. A package for constructive representation theory is [41].

4.3. The General Fourier Transform. With the machinery above, we can define the general Fourier transform which works for any finite group, abelian or nonabelian.

Definition 4.1 (Fourier Transform over a finite group). Let G be a finite group of order N, f : G → ℂ any map of sets. For an irreducible representation ρ of G of dimension d_{ρ}, define the Fourier transform of f at ρ to be

(73)  f̂(ρ) = \sqrt{\frac{d_{ρ}}{N}} ∑_{g∈G} f(g)ρ(g)

Let Ĝ be a complete set of irreducible representations of G. We define the inverse Fourier transform of f̂ to be

(74)  f(g) = \sqrt{\frac{1}{N}} ∑_{ρ∈Ĝ} \sqrt{d_{ρ}}tr (f̂(ρ)ρ(g^{−1}))

To ensure this definition makes sense, we check that the f(g) in the definition of the inverse is actually the f we started with, by substituting the definition of f̂ in the definition for the inverse, and swapping the order of summation, obtaining

(75)  \frac{1}{N} ∑_{g′∈G} f(g′) ∑_{ρ∈Ĝ} d_{ρ}tr (ρ(g′g^{−1})) = f(g),

where we note the rightmost sum is 0 by equation 72 unless g′ = g, in which case that sum is N, so the equality follows. Thus the definition agrees with the initial f.

To understand this as a Fourier transform, we associate f and f̂ with vectors in ℂ^{N}, and examine the map Γ : f → f̂. To do this, fix an ordering of G = {g_{1}, g_{2}, …, g_{N}}, and then f is equivalent to a vector we also label f,

f = (f(g_{1}), f(g_{2}), …, f(g_{N})) ∈ ℂ^{N}.

To view f̂ as a vector in ℂ^{N}, we need more choices. Fix an ordering Ĝ = {ρ_{1}, ρ_{2}, …, ρ_{m}}, let d_{k} = d_{ρ_{k}}, and for each ρ_{k} : G → GL(ℂ^{d_{k}}) fix a basis of ℂ^{d_{k}}, so each f̂(ρ_{k}) is a d_{k} × d_{k} matrix. Since ∑_{ρ} d_{ρ}^{2} = N, there are N matrix entries, which we order. For brevity label the matrix entry f̂(ρ_{k})_{ij} = f̂_{ijk}. Then we can associate f̂ with a vector

f̂ = (f̂_{111}, f̂_{121}, …, f̂_{d_{N} d_{N} m}) ∈ ℂ^{N}.

Viewing Γ : f → f̂ as a map from ℂ^{N} to itself, it is not hard to show Γ is linear. It is a good exercise to show Γ is a unitary transformation when viewed this way.

Note in the finite abelian case each irreducible representation is one dimensional, so each d_{ρ} = 1, and then the only representations are given by the characters in section 3.5. Then Γ becomes the finite abelian Fourier transform, and this definition generalizes the definition given earlier.

4.4. The Standard HSP Algorithm - Quantum Fourier Sampling. We now cover what is called the standard algorithm for finding hidden subgroups of a given group. The complexity and qubit requirements depend on the group in question; we will cover what is known in section 5. This section follows Hallgren [59] and Grigni, Schulman, Vazirani, and Vazirani [53].

The process about to be described is called Quantum Fourier Sampling, or QFS for short. It is the process of preparing a quantum state in a uniform superposition of states indexed by a group, then performing an oracle function, then a quantum Fourier transform, and finally sampling the resulting state to gather information about subgroups hidden by the oracle.

We first note the standard finite abelian group case can be summarized as: [Algorithm 1]

(1) Compute \frac{1}{\sqrt{|G|}} ∑_{g∈G} |g⟩|f(g)⟩ and measure the second register f(g). The

resulting superposition is then \frac{1}{\sqrt{|H|}} ∑_{h∈H} |ch⟩|f(ch)⟩ for some uniformly

chosen coset cH of H.

(2) Compute the Fourier transform of the coset state, obtaining in the first register

∑_{ρ∈Ĝ} \frac{1}{\sqrt{|G||H|}} ∑_{h∈H} ρ(ch)|ρ⟩

where Ĝ is the set of (irreducible) representations^{24} {ρ : G → ℂ}.

(3) Measure the register, and observe a representation ρ. This gives information about H.

(4) Classically process the information from the previous step to determine the hidden subgroup H.

We can generalize this to handle the nonabelian and abelian cases in one framework via

[Algorithm 2] (1) Compute \frac{1}{\sqrt{|G|}} ∑_{g∈G} |g⟩|f(g)⟩ and measure the second register f(g). The

24In the abelian case these are the same as the characters.

resulting superposition is then \frac{1}{\sqrt{|H|}} ∑_{h∈H} |ch⟩|f(ch)⟩ for some uniformly

chosen coset cH of H.

(2) Compute the Fourier transform of the coset state, obtaining in the first register

∑_{ρ∈Ĝ} ∑_{i}^{d_{ρ}} ∑_{j}^{d_{ρ}} \begin{matrix}√ & \overline{d_{ρ}} \\ √ & \overline{|G||H|} \end{matrix} ( ∑_{h∈H} ρ(ch))_{i,j} |ρ, i, j⟩

where Ĝ is the set of (irreducible) representations {ρ : G → ℂ}.

(3) Weak form: Measure the register, and observe a representation ρ. This gives information about H. Strong form: Measure the register, and observe a representation ρ as well as matrix indices i and j. This gives information about H.

(4) Classically process the information from the previous step to determine the hidden subgroup H.

This algorithm gives information useful for finding generators of the hidden subgroup H. Ignoring the problem of engineering the physical quantum computer, there are three theoretical obstacles to making this algorithm efficient for a given family of nonabelian groups. They are:

(1) We need an efficient way to compute the QFT over the groups in question, similar to the way that equation 36 led to an efficient quantum circuit computing the QFT over ℤ_{2^{n}}. Beals [14] constructs an efficient QFT for the symmetric groups, and Diaconis and Rockmore [39] construct efficient classical Fourier transforms over many other groups. For more information on the QFT see [90, 92, 91, 89] and section 5. Efficient QFT quantum circuits are not known for all finite groups.

(2) We need to choose a basis for the irreducible representations ρ ∈ Ĝ. For the abelian case, the irreducible representations are one dimensional characters, so the basis choices are canonical, so this step is trivial. However, in the nonabelian case some bases may give better results. For example, it is known the standard method cannot solve the HSP over S_{n} if the basis choice is random - it will take a clever basis choice for the irreducibles to obtain an efficient algorithm.

(3) We need an efficient way to reconstruct the subgroup generators for H from the irreducible representations returned. For the abelian case this is efficient since they are canonical and computing the GCD and solving linear systems mod d are efficient classically as explained in section 3.5. However, this reconstruction is harder in the nonabelian case. For example, Ettinger, Høyer, and Knill [46] have shown only polynomially many calls in log |G| to the oracle distinguishes subgroups for any group G information theoretically, but it is currently unknown how to extract generators for H without exponential classical postprocessing time.

One immediate question is if the weak and strong forms are equivalent. Section 5 shows the strong form can distinguish between certain subgroups which the weak form cannot. The reason is roughly that conjugate subgroups determine the same statistics on representations, but not on rows and columns, which gives more information. However, there are still cases where the weak form is good enough.

The next question is to ask which groups have efficient HSP algorithms, and are there any groups for which the HSP cannot be solved efficiently?

These questions are ongoing research problems, and there are partial results showing which groups are likely to be efficiently solvable, and some negative results showing limitations of this approach. The next section covers many known results and current research directions.

For more reading on the (classical) computation of FFT’s over finite groups, see Babai and Ronyai [5], Baum [9], Baum and Clausen [10, 11, 12], Baum, Clausen, and Tietz [13], Rockmore [108, 109, 110], and Terras [122].

5. Nonabelian Results

5.1. Overview. In this section we present results about the HSP over finite nonabelian groups. Throughout this section we fix notation: G is a member of a family of finite groups G = {G_{i}} that should be clear from context, and H is a subgroup of G. The size n of the problem is n = ⌈log |G|⌉ or sometimes n = O(log |G|), also clear from context. We say a quantum algorithm is efficient in either case if the circuit size is polynomial in n as G varies through the family.

We also divide families of groups into three classes (following Moore, Rockmore, Russell, and Schulman[97]):

I. Fully Reconstructible. Subgroups of a family of groups G = {G_{i}} are fully reconstructible if the HSP on G_{i} can be solved with probability > \frac{3}{4} by a quantum circuit of size polynomial in log |G_{i}|.

II. Measurement Reconstructible. Subgroups of a family of groups G = {G_{i}} are measurement reconstructible if the solution to the HSP on G_{i} is determined information-theoretically using the fully measured result of a quantum circuit of size polynomial in log |G_{i}|.

III. Query Reconstructible. Subgroups of a family of groups G = {G_{i}} are query reconstructible if the solution to the HSP for G_{i} is determined by the quantum state resulting from a quantum circuit of size polynomial in log |G_{i}|, in the sense that there is a POVM that yields the subgroup H with constant probability. There is no guarantee that this POVM can be implemented by a small quantum circuit.

A primary goal of quantum algorithm research is to move groups into lower numbered classes, and the driving force is to place all finite groups in class I. Currently very few group families are class I, but we will see all finite groups are in class III, with some moving up to class II and I. This is contrasted with what we saw above: all finite abelian groups are in class I. We will see examples of each of the three classes below.

5.2. A Necessary Result. In order to find an efficient quantum algorithm for a given family, it is necessary that O(poly(n)) oracle queries suffices. Fortunately this has been shown possible for any finite group by Ettinger, Høyer, and Knill[46, 47]. They prove that polynomially many oracle queries in n distinguishes subgroups information theoretically. They do this by creating the state

(76)  |ψ⟩ = \frac{1}{\sqrt{|G|^{m}}} ∑_{(g_{1},g_{2},...,g_{m})∈G^{m}} |g_{1}, g_{2}, …, g_{m}⟩|f(g_{1}), f(g_{2}), …, f(g_{m})⟩

which requires m oracle queries. Taking m = ⌈4n + 2⌉ results in a state from which H can be extracted with high probability, unfortunately requiring O(|G|) operations to do so. Precisely, they prove

Theorem 5.1. Let G be a finite group, and f an oracle function on G which separates a subgroup H. Then there exists a quantum algorithm that calls the oracle function ⌈4 log |G| + 2⌉ times and outputs a subset X ⊆ G such that X = H with probability at least 1 − 1/|G|.

So for any finite group G and subgroup H it is possible to gather enough information to determine H using only O(poly(log |G|)) queries of f, thus placing all finite groups in class III. Their proof is reproduced in section 5.7 since it is foundational.

5.3. The Dihedral Group D_{N}. Many attempts have been made to find an efficient HSP algorithm for the dihedral groups. One reason is that it one of the “simplest” nonabelian groups and is easily studied. Another reason is that they have exponentially many (in n) subgroups of small order, making classical algorithms infeasible^{25}. A better reason is that an efficient HSP algorithm for the dihedral groups gives efficient algorithms for solving some classically hard lattice problems [107], which is covered below. Recall ℤ_{N} is a cyclic group on N elements^{26}. Then we define the dihedral group D_{N} = ℤ_{2} ⋉ ℤ_{N} with 2N elements and with relations

(77)  x^{N} = y^{2} = yxyx = 1.

5.3.1. Equivalent Problems. Before we start on dihedral group algorithms, we remark Kuperberg [82] lists equivalences between the Dihedral HSP (DHSP) and other problems. Precisely we define the DHSP as finding a hidden subgroup H that is either trivial or generated by a reflection H = ⟨x^{s}y⟩. This is equivalent to the general problem of determining subgroups of D_{N} as we outline below in section 5.3.2.

Next we define the abelian hidden shift problem to be: given an abelian group A, a set S, and two injective functions f, g : A → S that differ by a hidden shift s

(78)  f(v) = g(v + s)

and are otherwise distinct, then determine s (using quantum oracles f and g).

The DHSP is equivalent to the abelian hidden shift problem with A = ℤ_{N}. If we define h : D_{N} → S by

(79)  h(x^{n}) = f(n) h(x^{n}y) = g(n),

then h hides the reflection x^{s}y. Solving the DHSP for h gives s, solving the shift problem. Conversely, given the DHSP h : D_{N} → S, define f, g as in equation 79. Then a solution to the abelian hidden shift problem for f and g determines s, which determines the subgroup H hidden by h.

Generally, the a solution to the HSP on G = ℤ_{2} ⋉ A where ℤ_{2} acts by inversion on A is equivalent to the abelian hidden shift problem on A.

The cyclic hidden reflection problem is: h : ℤ_{N} → S satisfies

(80)  h(n) = h(s − n)

25For example, it takes exponentially many evaluations of f just to determine if H is nontrivial with probability bounded above 1/2. This holds for the reasons in Simon[119]

26We could abstractly call C_{N} the cyclic group on N elements, but then C_{N} ≅ ℤ_{N}, not always canonically. We choose the concrete ℤ_{N}.

and otherwise takes distinct values. We want to find s. This problem is equivalent to the DHSP; we show it equivalent to the abelian hidden shift problem as follows.

It reduces to the shift problem by defining the ordered pairs

(81)  f(n) = (h(−n), h(−n − 1)) g(n) = (h(n), h(n + 1)).

We need pairs to ensure f and g are injective. Then f(n) = g(s+n) and are distinct otherwise, giving the reduction.

Conversely, if f, g : ℤ_{N} → S are injective and

(82)  f(n) = g(s + n)

then we can define the unordered pairs

(83)  h(n) = {f(−n), g(n)} .

which reduces the hidden reflection problem to the shift problem. Note h(n) = {f(−n), g(n)} = {g(s − n), f(n − s)} = {f(−(s − n)), g(s − n)} = h(s − n).

5.3.2. Dihedral Results. Now we cover what is known about the DHSP.

Ettinger and Høyer [45] show an algorithm that produces data sufficient to determine any hidden subgroup H in a dihedral group D_{N}, but it is unknown if this data can be post processed in O(poly(n)) time to reconstruct the subgroup H. This is stronger than the result in [43] since it returns the classical data from the quantum state. [43] only constructed a state determining H, but required exponential time to extract that information to classical information. Their algorithm exploits the normality of the (abelian) cyclic group ℤ_{N} < D_{N}, and uses the abelian QFT to gather information which is then extended to determine the subgroup H. They reduce to the case of finding a subgroup H generated by a reflection. They prove

Theorem 5.2. Let f be a function that separates H in the dihedral group D_{N}. There exists a quantum algorithm that uses Θ(log N) evaluations of f and outputs a subset X ⊆ H such that X is a generating set for H with probability at least 1 − \frac{2}{N}.

Following Ettinger and Høyer [45], we outline the proof that it is sufficient to solve the DHSP for the simpler case where H is either trivial or generated by a reflection. We want to find the hidden subgroup H < D_{N}, where we view D_{N} as the semidirect product ℤ_{N} ⋊ ℤ_{2}. Using the abelian QFT algorithm, we find H_{1} = H ∩ {ℤ_{N} × {0}}, which is normal in D_{N}. Then we work on the quotient group D_{N}/H_{1} ≅ D_{M} with M = [ℤ_{N} × {0} : H_{1}], and find H/H_{1} which is either generated by a reflection r + H_{1} or is trivial. Precisely,

Theorem 5.3. Let f be a function that separates H in the dihedral group D_{N}, and suppose we are promised that H = {0} is trivial or H = {0, r} is generated by a reflection r. Then there exists a quantum algorithm that given f, outputs either “trivial” or the reflection r. If H is trivial , the output is always trivial, otherwise the algorithm outputs r with probability at least 1− \frac{1}{2N}. The algorithm uses at most 89 log_{2}(N) + 7 evaluations of f and it runs in time O(\sqrt{N}).

Finally, Kuperberg [82] gives a subexponential time quantum algorithm for solving the dihedral HSP, using time and query complexity O(exp(C\sqrt{log N})) for D_{N}. This is much better than the classical query complexity of O(\sqrt{N}). Unfortunately this algorithm requires Θ(exp(C\sqrt{log N})) quantum space. Variants of this algorithm also work for the abelian hidden shift problem described above and for the hidden substring problem^{27}. The main results are

Theorem 5.4. There is an algorithm that finds a hidden reflection in the dihedral group G = D_{N} (of order 2N) with time and query complexity O(exp(C\sqrt{log N})).

Theorem 5.5. The abelian hidden shift problem has an algorithm with time and query complexity O(exp(C\sqrt{n})) where n is the length of the output, uniformly for all finitely generated abelian groups.

(Note this is even true for infinite groups; we only need finitely generated!)

Corollary 5.6. The N ↪ 2N hidden substring problem has an algorithm with time and query complexity O(exp(C\sqrt{log N}).

5.4. Groups with an Efficient QFT. Next we turn to some other groups with an efficient QFT. To use the standard weak or strong form of the algorithm, we need to be able to compute efficiently the Fourier transform of a function over a given group. So in this section we list some of the groups for which efficient quantum Fourier transform algorithms are known.

Zalka [129] gives an algorithm for the HSP on wreath product groups G = ℤ_{2}^{n}≀ℤ_{2}. The idea is similar to Ettinger and Høyer [45], in that it finds generators for an abelian subgroup in the desired subgroup, and then extends it.

Høyer [64] shows how to construct QFT for many groups: quaternions, a class of metacyclic^{28} groups (up to phase), and a certain subgroup E_{n} of the orthogonal group O(2^{n}) useful for quantum error correction [26].

Beth, Püschel, Rötteler, [20] show how to do the QFT efficiently on a class of groups - solvable 2 groups containing a cyclic normal subgroup of index 2 (|G| is a power of 2 and solvable): They give reference to the fact for n ≥ 3 there are exactly 4 isomorphism classes of such nonabelian groups of order 2^{n+1} with a cyclic subgroup of order 2^{n}:

• the dihedral group D_{2^{n+1}} = ⟨x, y | x^{2^{n}} = y^{2} = 1, yxyx = 1⟩,

• the quaternion group Q_{2^{n+1}} = ⟨x, y | x^{2^{n}} = y^{4} = 1, y^{3}xyx = 1⟩,

• the quasi-dihedral group QD_{2^{n+1}} = ⟨x, y | x^{2^{n}} = y^{2} = 1, yxy = x^{2^{n−1}−1}⟩,

• the group QP_{2^{n+1}} = ⟨x, y | x^{2^{n}} = y^{2} = 1, yxy = x^{2^{n−1}+1}⟩.

Beals [14] shows how to compute the QFT over S_{n} in time O(poly(n)), by adapting the methods of Clausen [30] and Diaconis-Rockmore [39] to the quantum setting.

Moore, Rockmore, and Russell [96] show how to construct efficient quantum Fourier transform circuits of size O(poly log |G|) for many groups, including

• the Clifford groups ℂ𝕃_{n},

• the symmetric group, recovering Beals algorithm [14],

• wreath products G ≀ S_{n}, where |G| = O(poly(n)),

• metabelain groups (semidirect products of two abelian groups), including metacyclic groups such as the dihedral and affine groups, recovering the algorithm of Høyer [64], • bounded extensions of abelian groups such as the generalized quaternions,

27See the paper for a precise definition. It is basically a string matching algorithm.

28A group G is metacyclic if it contains a cyclic normal subgroup H such that the quotient group G/H is cyclic.

recovering the algorithm of Püschel et al. [20]. Their results also give subexponential size quantum circuits for the linear groups GL_{k}(q), SL_{k}(q), PGL_{k}(q), PSL_{k}(q), for a fixed prime power q, finite groups of Lie type, and the Chevalley and Weyl groups. Unfortunately, defining polynomially uniform, adapted diameter, homothetic, and multiplicity would take us too far afield; see their paper for details. These have to do with certain group items being efficiently computable. But we state their two main theorem anyway:

Theorem 5.7. If G is a polynomially uniform group with a subgroup tower G = G_{m} > G_{m−1} > ⋯ > 1 with adapted diameter D, maximum multiplicity M, and maximum index I = max_{i}[G_{i} : G_{i−1}], then there is a quantum circuit of size poly(I × D × M × log |G|) which computes the quantum Fourier transform over G.

Theorem 5.8. If G is a homothetic extension of H by an abelian group, then the quantum Fourier transform of G can be obtained using O(poly log |G|) elementary quantum operations.

5.5. HSP Algorithms and Groups.

5.5.1. Group Definitions I. H is a subgroup of G; let N(H) or N_{G}(H) be the normalizer of H in G. Let M_{G} be the intersection of all normalizers in G, i.e., M_{G} = ⋂_{H≤G} N(H). M_{G} is a subgroup of G and can be taken to be the size of how nonabelian G is ([G : M_{G}] = 1 for abelian groups). H^{G} is the largest subgroup of H that is normal in G, and is called the normal core of H.

Definition 5.9 (Wreath Product). The wreath product of two finite groups G and H is defined as follows. For |H| = n, view H a subgroup of the symmetric group S_{n} on n items. Let P = G × ⋯ × G be the direct product of n copies of G. The wreath product G ≀ H of G with H is a semidirect product P ⋊ H with multiplication

(84)  (g_{1}, …, g_{n}; τ) (g′_{1}, …, g′_{n}; τ′) = (g_{τ′(1)}g′_{1}, …, g_{τ′(n)}g_{n}; ττ′)

That is, the permutations in H are composed as usual, but the right permutation permutes the left factors of P and then the n-tuple is multiplied pointwise. It is instructive to verify this operation forms a group.

5.5.2. Normal Subgroups Can be Found in Any Group. Hallgren, Russell, and Ta-Shma (2002) [59] prove that the natural extension of the abelian case algorithm finds H^{G} efficiently, the normal core of H. This also gives that normal subgroups can be found efficiently by the standard (weak or strong version of the) algorithm. In particular, this allows finding hidden subgroups in Hamiltonian groups (groups whose subgroups are all normal); the nonabelian Hamiltonian groups are of the form ℤ_{2}^{k} × B × Q, where Q is the 8 element quaternion group and B is an abelian group with exponent^{29} b coprime with 2. See Rotman [111, Exercise 4.28]. They show the probability of measuring a representation ρ is independent of the coset of H.

29Recall the exponent a of a group G is the smallest integer a such that g^{a} = e, the identity, for every element g ∈ G, if such an integer exists.

Theorem 5.10. The probability of measuring the representation ρ in Algorithm 2 of section 4.4 is d_{ρ} \frac{|H|}{|G|} times the number of times ρ appears in Ind_{H}^{G}1_{H}.

They also obtain:

Theorem 5.11. Let H be an arbitrary subgroup of G, and let H^{G} be the largest subgroup of H that is normal in G. With probability at least 1−2 exp(− log_{2} |G|/8), H^{G} is determined by observing O(log |G|) independent trials of QFS.

In fact, if ρ_{1}, …, ρ_{m} are the representations sampled by m repetitions of the algorithm, then H^{G} = ⋂_{i} ker ρ_{i} with high probability.

They also show that weak QFS does not distinguish between order 1 and 2 subgroups in S_{n}:

Theorem 5.12. For S_{n}, there is a subgroup H_{n} so that the weak QFS does not distinguish (even information theoretically) the case that the hidden subgroup is trivial from the case the hidden subgroup is H_{n}. Specifically, the distributions induced on representations in these two cases have exponentially small total variation distance.

Theorem 5.13. Let H be an arbitrary subgroup of G, and let H^{G} be the largest subgroup of H that is normal in G. With probability at least 3/4, H^{G} is uniquely determined by observing m = O(log |G|) independent trials of Algorithm 2 of section 4.4 when H is the hidden subgroup. When H is normal, H^{G} = H, and this determines H.

5.5.3. “Almost Abelian” Subgroups Can be Found and Measuring Rows is Strong Enough. Grigni, Schulman, Vazirani, and Vazirani [53] show another class of groups for which the HSP has an efficient quantum solution - what they call “almost abelian” groups. These are groups for which the intersection M(G) of all the normalizers of all subgroups of G is large. For n = log |G|, they require [G : M(G)] (called the Baer norm [97]) to be of order exp O(log^{1/2} n), and then the HSP can be solved if the QFT can be performed efficiently. In particular they show that the subgroups of the semidirect product ℤ_{m} ⋉ ℤ_{3} for m a power of 2 can be found efficiently.

Another useful result in their paper shows that measuring both the row and column in the strong form of the QFT gives no more information than measuring just one of them (depending on how one lets the irreps act - left or right). This follows from the quantum mechanical requirement that the irreps are unitary matrices, and thus each matrix row (or column) has the same norm, which gets “absorbed.”

Most importantly, they show that even using the strong form with a random basis for the irreps, the strong QFS algorithm cannot distinguish between the case of a trivial subgroup and an order two subgroup without exponentially many oracle queries.

The restriction on the size of M(G) was extended by Gavinsky [51] to allow [G : M(G)] to be of size O(poly(n)), allowing the corresponding HSP to be solved efficiently if the QFT over G can be. These groups are labelled “poly-near-hamiltonian groups.” A final algorithm in this paper shows how to solve the HSP efficiently on poly-near hamiltonian groups even when the QFT over the group G is not known to be efficient, by using QFS over a hamiltonian group, which was shown to be efficient by a result from above.

5.5.4. Strong is Indeed Stronger. Moore, Rockmore, Russell, and Schulman [97] show that the strong form is indeed stronger, by exhibiting semidirect products ℤ_{q} ⋉ℤ_{p} (the q-hedral groups, which include the affine groups A_{p} ≅ ℤ_{p}^{∗} ⋉ℤ_{p}) , where q|(p − 1) and q = p/polylog(p), such that the strong form can determine hidden subgroups efficiently, but the weak form and “forgetful” abelian form cannot. They also prove a closure property for the class of groups over which the HSP can be solved efficiently:

Theorem 5.14. Let H be a group for which hidden subgroups are fully reconstructible, and K a group of size polynomial in log |H|. Then hidden subgroups in any extension of K by H, i.e. any group G with K ◁ G and G/K ≅ H, are fully reconstructible.

They also place some groups in class I.

Theorem 5.15. Let p be a prime, q a positive integer, and G = ℤ_{q} ⋉ ℤ_{p}. Then

(1) if q is prime and q = (p − 1)/polylog(p), then subgroups of G are fully reconstructible (class I),

(2) if q divides p−1, then hidden conjugates of H in G are fully reconstructible (class I) if H has index polylog(p),

(3) if q divides p − 1, then hidden conjugates of H in G are measurement reconstructible (class II),

(4) if q divides p − 1, then subgroups the q-hedral groups G are measurement reconstructible (class II). In particular, the subgroups of the affine groups A_{p} = ℤ_{p−1}^{∗} ⋉ ℤ_{p} are measurement reconstructible (class II).

For another direction studying the HSP over infinite groups, see Lomonaco and Kauffman [85]. They consider a version of the HSP for finding periods of functions over the real numbers ℝ, although it is not clear if these could be physically implemented due to ℝ being an infinite set. They have a good overview of the HSP in [84].

Rötteler and Beth [112] give an efficient algorithm solving the HSP on wreath products W_{n} = ℤ_{2}^{n} ≀ ℤ_{2} (like Zalka) by giving quantum circuits for the QFT and showing how to reconstruct the subgroup efficiently from samples. It uses O(n) queries of f and O(poly(n)) classical post processing time, putting these groups in Class I. It is similar to the method of Ettinger and Hoyer.

In [43] Ettinger and Høyer construct a quantum observable for the graph isomorphism problem. Given two graphs of n vertices and an integer m, they define a quantum state on O(mn) qubits, that when observed, outputs “yes” with certainty if the graphs are isomorphic and “no” with probability at least 1 − \frac{n!}{2^{m}} if they are not isomorphic. It is unknown if this observable can be implemented efficiently.

Cleve and Watrous [33] show how to reduce the complexity and size of the QFT for ℤ_{2^{n}}.

Theorem 5.16. For any m there is a quantum circuit that exactly computes the QFT modulo 2^{m} that has size O(m(log m)^{2} log log m) and depth O(m).

Theorem 5.17. For any m and ϵ there is a quantum circuit that approximates the QFT modulo 2^{m} that has size O(m log(m/ϵ)) and depth O(log m + log log(1/ϵ)).

They give an upper bound.

Theorem 5.18. Any quantum circuit consisting of one- and two- qubit gates that approximates the QFT with precision \frac{1}{10} or smaller must have depth at least log n.

5.5.5. Lattice Problems. Regev [107] shows that an efficient algorithm solving the HSP for dihedral groups would result in efficient algorithms for solving the Unique Shortest Vector Problem (SVP) and the subset-sum problem. First we sketch some definitions. A lattice is the set of all integral linear combinations of k linearly independent vectors in ℝ^{k}. This set of k vectors is called the basis of the lattice. The SVP is the problem of finding the shortest nonzero vector in this lattice, given the basis. In the f(k)-unique-SVP we are given the promise that the shortest vector is shorter by at least a factor of f(k) from all other non-parallel vectors. We also define the Dihedral Coset problem (DCP). The input to the DCP for the dihedral group D_{N} of order 2N is a tensor product of polynomially many (in N) registers, each with the state |0, x⟩ + |1, (x + d (mod N))⟩ for some arbitrary x ∈ {0, 1, …, N − 1}, and d is the same for all registers. The goal is to find d. We say the DCP has failure parameter α if each of the registers with probability at most \frac{1}{(log n)^{α}} is in the state |b, x⟩ for arbitrary b. We take N = k, so the dihedral group size is determined by the dimension of the lattice. The main theorem is then

Theorem 5.19. If there exists a solution to the DCP with failure parameter α then there exists a quantum algorithm that solves the Θ(k^{\frac{1}{2} +2α})-unique-SVP.

Thus an efficient Dihedral HSP algorithm would give an efficient f(k)-unique-SVP algorithm.

5.5.6. Distinguishable Subgroups of S_{n}. Kempe and Shalev [74] analyze which subgroups of S_{n} can be distinguished efficiently using QFS. H < S_{n} is primitive if it is transitive, and does not preserve a non-trivial partition of the permutation domain. They show

Theorem 5.20. Let H ≠ A_{n}, S_{n} be a subgroup of S_{n}, with H a primitive subgroup. Then H is indistinguishable.

Theorem 5.21. A subgroup H < S_{n} with property Υ (below) can be efficiently distinguished from the identity subgroup using either the weak or strong standard method with random basis only if it contains an element of constant support (i.e., a permutation in which all but a constant number of points are fixed). Property Υ can be any of the following

• H is of polynomial size,

• H is primitive.

They also show other properties Υ for which the statement is true, and conjecture it is true for all subgroups of S_{n}. If their conjecture is true, which amounts to proving the following conjecture, then QFS with random basis provides no advantage over classical search. The minimal degree of a subgroup H < S_{n} is defined to be the minimal number of points moved by a non-identity element of H. The support of an element is the number of points moved. Then the conjecture is

Conjecture 5.22. Every subgroup H < S_{n} with non-constant minimal degree has at most n^{k/7} elements of support k.

5.6. Black-Box Group Algorithms.

5.6.1. Black-box Group Algorithms. Black-box groups were introduced by Babai and Szemerédi in 1984 [6]. In the context of black-box groups, each group element is encoded as a length n = O(log |G|) string, and we assume group operations (multiplication, inverse, identity testing) are preformed by a group oracle (or blackbox) in unit time. If each element is represented by a unique string this is called the unique encoding model, otherwise it is not unique encoding. A black-box group without unique encoding augmented by an oracle that can recognize any encoding of the identity element in unit time can compare elements for equality in unit time. Any efficient algorithm in the context of black-box groups remains efficient whenever the group oracle can be replaced by an efficient process. It is provably impossible to compute group orders in polynomial time in size log of the group, even for abelian groups. This becomes possible using quantum algorithms, as we will see. A black-box group G is defined by a set of m generators, each of length n bits, i.e., G = ⟨g_{1}, g_{2}, …, g_{m}⟩. The quantity mn is called the input size for the group. Throughout this section on black-box group algorithms we reserve n to denote the length of the strings representing the finite group G, and all groups are finite.

5.6.2. Group Definitions. To state results for black-box group algorithms we need more definitions. Given a group G and elements g, h ∈ G, we define the commutator of g and h, denoted [g, h], to be [g, h] = g^{−1}h^{−1}gh, and for any two subgroups H, K ≤ G we write [H, K] to denote the subgroup of G generated by all commutators [h, k] for h ∈ H and k ∈ K. The derived subgroup (also known as the commutator subgroup) of G is G′ = [G, G], and we write

G^{(0)} = G,
G^{(j)} = (G^{(j−1)})′ , for j ≥ 1.

A group G is said to be solvable if G^{(m)} = {1} (the trivial group) for some value of m.

A composition series for G is a sequence of subgroups of G = G_{1}▷G_{2} ⋯▷G_{t} = 1 such that G_{i+1} is normal in G_{i}, and the factor groups G_{i}/G_{i+1} are simple. The factor groups G_{i}/G_{i+1} are unique up to isomorphism and ordering. Beals and Babai [4] define v(G) as the smallest natural number v such that every nonabelian composition factor of G possesses a faithful permutation representation of degree at most v. Thus for a solvable group v(G) = 1 (solvable implies factor groups are cyclic, hence abelian, hence have only trivial irreducible representations). It is known that v(G) is polynomially bounded in the input size in many important cases, such as permutation groups or matrix groups over algebraic number fields.

A presentation of G is a sequence g_{1}, …, g_{s} of elements generating G, together with a set of group expressions in variables x_{1}, …, x_{s} called relations, such that g_{1}, …, g_{s} generate G and the kernel of the homomorphism from the free group F (x_{1}, …, x_{s}) → G given by x_{i} → g_{i} is the smallest normal subgroup of F containing the relations. This gives a non-canonical yet very concrete description of G as the set of “strings” of the g_{i} and equivalence relations on those strings. Note the generators in the presentation may differ from the original generators given for G.

A nice representation of a factor group G_{i}/G_{i+1} means a homomorphism from G_{i} with kernel G_{i+1} to either a permutation group of degree polynomially bounded in the input size + v(G) or to ℤ_{p}, where p is a prime dividing |G|.

The exponent of a group is the smallest integer m such that g^{m} = e for all g ∈ G. Lagrange’s theorem gives m ≤ |G|.

An abelian group (family) is smoothly abelian if it can be decomposed into the direct product of a subgroup of bounded exponents and a subgroup of polylogarithmic size in the order of the group. A solvable group (family) is smoothly solvable if its derived series is of bounded length and has smoothly abelian factor groups.

A constructive membership test is the following: given pairwise commuting group elements h_{1}, h_{2}, …, h_{r}, g of a group G, either express g as a product of powers of the h_{i}’s or report that no such expression exists.

5.6.3. Results. Our first result [28], the basis for many later ones, allows computing a canonical decomposition of a finite abelian group from a generating set in polynomial time, i.e.,

Theorem 5.23 (Cheung, Mosca). Given a finite abelian black-box group G with unique encoding, the decomposition of G into a direct sum of cyclic groups of prime power order can be computed in time polynomial in the input size by a quantum computer.

Watrous [125] shows how to construct quantum certificates proving group nonmembership efficiently, and shows this is not possible classically.

Watrous [126] gives a polynomial-time quantum algorithm for computing the order of a solvable group, which gives polynomial-time algorithms for membership testing of an element in a subgroup, testing subgroup equality given two descriptions of the subgroups, and testing subgroup normality, each for solvable groups. The main result is

Theorem 5.24 (Group Order). Given a finite, solvable black-box group G, there exists a quantum algorithm that outputs the order of G with probability of error bounded by ϵ in time polynomial in the input size + log(1/ϵ). The algorithm produces a quantum state ϕ that approximates the state |G⟩ = |G|^{−1/2} ∑_{g∈G} |g⟩ with accuracy ϵ in the trace norm metric.

This result was also obtained using a different algorithm by Ivanyos et. al. [66] in a paper extending many of the black-box group results from Beals-Babai [4] to the quantum setting. They obtain

Theorem 5.25. Let G be a finite black-box group with not necessarily unique encoding. Assume the following are given:

(a) an oracle for computing the orders of elements of G,

(b) an oracle for the constructive membership tests in elementary abelian

subgroups of G.

Then the following tasks can be solved by quantum algorithms of running time polynomial in the input size+v(G):

(1) constructive membership tests in subgroups of G,

(2) computing the order of G and a presentation for G,

(3) finding generators for the center of G,

(4) constructing a composition series G = G_{1}▷G_{2}▷⋯▷G_{t} = 1 for G, together with nice representations of the composition factors G_{i}/G_{i+1},

(5) finding Sylow subgroups of G.

The hypotheses (a) and (b) can be met in many cases. For example, using Shor’s order finding method to compute element orders, they give:

Theorem 5.26. Assume G is a black-box group with unique encoding. Then each task in theorem 5.25 can be solved in time polynomial in the input size + v(G) by a quantum algorithm.

Theorem 5.27. Assume G is a black-box group with not necessarily unique encoding, and that N is a normal subgroup given as a hidden subgroup of G (i.e., there is a f hiding N). Then there are quantum algorithms each with running time polynomial in the input size + v(G/N) that perform:

• all the tasks in theorem 5.25 for G/N,

• finding generators for N. In particular, we can find hidden normal subgroups of solvable black-box groups and permutation groups in polynomial time in input size + v(G/N) (note we do not need an efficient QFT as in Hallgren et. al. [59]),

If instead of giving N as a hidden subgroup, if N is given by generators, and N is solvable or of polynomial size, then all the tasks listed in theorem 5.25 can be solved for G/N in time polynomial in the input size + v(G).

Theorem 5.28. Let G be a black-box group with unique encoding. The HSP can be solved by a quantum algorithm in time polynomial in the input size + |G′|, the size of the commutator subgroup of G.

This includes the wreath products ℤ_{2}^{k} ≀ ℤ_{2} of Rötteler and Beth [112].

A question remains: the above proofs only use the abelian QFT to get the results. Does using the nonabelian QFTs give better results?

Friedl et. al. [49] introduced the Orbit Coset problem as a generalization of the hidden subgroup and hidden shift^{30} problems. Hidden shift was defined above in section 5.3.1. As mentioned there, when G is abelian, hidden shift is equivalent to the HSP in the semidirect product G ⋊ ℤ_{2}.

Definition 5.29 (Orbit Coset and Orbit Superposition). Let G be a finite group acting on a finite set Γ of mutually orthogonal quantum states.

• Given generators for G and two quantum states |ϕ_{0}⟩, |ϕ_{1}⟩ ∈ Γ, the problem Orbit Coset is to either reject the input if G(|ϕ_{0}⟩) ∩ G(|ϕ_{1}⟩) = ∅, or output a generating set for G_{|ϕ_{1}⟩} of size O(log |G|) and a u ∈ G such that |u · ϕ_{1}⟩ = |ϕ_{0}⟩.

• Given generators for G and a quantum state |ϕ⟩ ∈ Γ, the problem Orbit Superposition is to construct the uniform superposition |G · ϕ⟩ = \frac{1}{\sqrt{|G(|ϕ⟩)|}} ∑_{|ϕ′⟩∈G(|ϕ⟩)} |ϕ′⟩

Theorem 5.30. Let p be a fixed prime. Then

• the problem of hidden shift over ℤ_{p}^{m} can be solved in quantum polynomial time,

• the problem of Hidden Subgroup over ℤ_{p}^{m} ⋊ ℤ_{2} can be solved in quantum polynomial time.

This gives that Z_{p}^{m} ⋊ ℤ_{2} is class I for any prime p.

30Hidden shift is called hidden translation in their paper.

Theorem 5.31. Let G be a smoothly solvable group and let α be a group action of G. When t = (log^{Ω(1)} |G|) log(1/ϵ), Orbit Coset can be solved in G for α^{t} in quantum time poly(log |G|) log(1/ϵ) with error ϵ.

Using this they then show

Theorem 5.32. Hidden shift can be solved over smoothly solvable groups in quantum polynomial time. HSP can be solved in solvable groups having smoothly solvable commutator subgroups quantum polynomial time.

Fenner and Zhang [48] also address black-box group algorithms, obtaining efficient quantum algorithms for a few classically hard problems, by reducing them to Orbit Coset problems. The problems they study are Group Intersection (given two subsets S_{1} and S_{2} of a group, determine if the groups ⟨S_{1}⟩ ∩ ⟨S_{2}⟩ ≠ ∅), Coset Intersection (given two subsets S_{1} and S_{2} of a group and a group element g, determine if ⟨S_{1}⟩ g ∩ ⟨S_{2}⟩ ≠ ∅), and Double-Coset Membership (given two subsets S_{1} and S_{2} of a group and group elements g, h, determine if g ∈ ⟨S_{1}⟩ h ⟨S_{2}⟩).

They obtain

Theorem 5.33. Group Intersection over solvable groups can be solved efficiently in quantum polynomial time if one of the underlying solvable groups has a smoothly solvable commutator subgroup.

Theorem 5.34. Group Intersection over solvable groups is reducible to Orbit Superposition in quantum polynomial time.

Theorem 5.35. Coset Intersection and Double-Coset Membership over solvable groups can be solved in quantum polynomial time if one of the underlying groups is smoothly solvable.

van Dam, Hallgren, and Ip [62] work on a hidden shift problem They first obtain a superposition result (ignoring the normalization constant):

Theorem 5.36. Let f : G → ℂ be a complex valued function defined on the set G such that f(x) has unit magnitude whenever f(x) is nonzero. Then there is an efficient algorithm for creating the superposition ∑_{x} f(x)|x⟩ with success probability equal to the fraction of x such that f(x) is nonzero and that uses only two queries to the function f.

The proof idea computes the state ∑_{x} |x⟩|f(x)⟩, tests if f(x) is nonzero, moves the phase of |f(x)⟩ into |x⟩ to high precision, and then applies the second f to undo the first.

Let m be an integer, m = p_{1}^{s_{1}}p_{2}^{s_{2}} … p_{k}^{s_{k}}, then by the Chinese Remainder Theorem, (ℤ/mℤ)^{∗} ≅ (ℤ/p_{1}^{s_{1}}ℤ)^{∗}×(ℤ/p_{2}^{s_{2}}ℤ)^{∗} … (ℤ/p_{k}^{s_{k}}ℤ)^{∗}. A multiplicative character χ on ℤ/mℤ can be written as χ(x) = χ_{1}(x_{1})χ_{2}(x_{2}) … χ_{k}(x_{k}) using this isomorphism, where χ_{i}(x_{i}) is a multiplicative character on (ℤ/p_{i}^{s_{i}}ℤ)^{∗}. We say χ is completely nontrivial if each χ_{i} is nontrivial. With this definition, they then solve some shifted character problems:

Theorem 5.37. Given a nontrivial (resp. completely nontrivial) multiplicative character χ of a finite field 𝔽_{q} (where q = p^{r} for some prime p) (resp. over ℤ/mℤ), and a function f for which there is a shift s with f(x) = χ(x + s) for all x ∈ 𝔽_{q} (resp. x ∈ ℤ/mℤ). Then there is an efficient quantum algorithm finding s with probability 1 − 1/q^{2} (resp. (\frac{ϕ(m)}{m})^{3} = Ω((\frac{1}{log log m})^{3})).

In the case where m is unknown, this can still be done given a bound on m.

5.7. Hidden Subgroups are Distinguishable. In this section we show that at least information theoretically, it is possible to find any hidden subgroup H of a finite group G with only ⌈4 log |G| + 2⌉ calls to the oracle function f, following [46] and done differently in [47]. Unfortunately, deducing H from the resulting quantum state requires exponential classical time, and it is still open for which groups this can be reduced to a polynomial time quantum algorithm. The idea is to create a quantum state that contains enough information to deduce H using few oracle calls, and then use |G| applications of various measurements to this state to query each element of G. The technical work is to prove the measurements do not perturb the state too much, which would destroy information needed for later queries.

Precisely we prove:

Theorem 5.38. Given a finite group G and an oracle function f : G → X to a set X, such that f separates cosets of a subgroup H < G (f “hides” H). Then there exists a quantum algorithm that calls the oracle function ⌈4 log |G| + 2⌉ times and outputs a subset S ⊆ G, such that S = H with probability at least 1 − 1/|G|.

Proof. Fix a positive integer m. We work over the Hilbert space H of dimension |G|^{m}, with orthonormal basis indexed by m-tuples of elements of G. For any subset S = {s_{1}, s_{2}, …, s_{k}} ⊆ G let |S⟩ be the normalized superposition |S⟩ = \frac{1}{\sqrt{k}} (|s_{1}⟩ + … |s_{k}⟩). The first step is to prepare on H ⊗ H the state

(85)  \frac{1}{\sqrt{|G|^{m}}} ∑_{g_{1},...,g_{m}∈G} |g_{1}, …, g_{m}⟩|f(g_{1}), …, f(g_{m})⟩

where we define |f(g_{i})⟩ = |g_{i}H⟩. Note this required m calls to the function f. Observing the second register leaves in the first register the state |Ψ⟩ which is a tensor product of random left cosets of H, uniformly distributed. We ignore the second register for the rest of this proof. Let |Ψ⟩ = |a_{1}H⟩ ⊗ ⋯ ⊗ |a_{m}H⟩ denote the first register, where the a_{i} ∈ G. For any (ordered) subset {b_{1}, …, b_{m}} ⊆ G and subgroup K ≤ G define

(86)  |Ψ(K, {b_{i}})⟩ = |b_{1}K⟩ ⊗ |b_{2}K⟩ ⊗ ⋯ ⊗ |b_{m}K⟩

The key lemma, lemma 5.39, shows for K ≰ H that ⟨Ψ|Ψ(K, {g_{i}})⟩ is exponentially small for any m of the g_{i}.

Let H_{K} be the subspace of H spanned by all vectors of the form |Ψ(K, {g_{i}})⟩ for all subsets {g_{1}, …, g_{m}} ⊆ G. Let P_{K} be the projection operator^{31} onto H_{K}, and P_{K}^{⊥} the projection onto the orthogonal complement of H_{K} in H. Define the observable A_{K} = P_{K} − P_{K}^{⊥}, and fix an ordering g_{1}, g_{2}, …, g_{|G|} of G.

The algorithm then works as follows: First apply A_{⟨g_{1}⟩} to |Ψ⟩, where ⟨g⟩ ≤ G denotes the cyclic subgroup generated by g ∈ G. If the outcome is -1, then we know g_{1} ∉ H with certainty, and if the outcome is +1 we know g_{1} ∈ H with high probability, by lemma 5.39. We then apply A_{⟨g_{2}⟩} to the state resulting from the first measurement. Continuing in this manner, we test all elements of G for membership in H by sequentially applying A_{⟨g_{2}⟩}, A_{⟨g_{3}⟩}, and so on to the resulting states of the previous measurements. Of course if we discover g ∈ H then we can omit the tests for g^{j} ∈ H. Note we may have to apply O(|G|) operations to test each element, making the algorithm complexity exponential in log |G|. All that remains to show is that each measurement alters the state insignificantly with high probability, so that by the final operator A_{⟨g_{|G|}⟩} we have identified with high probability exactly which elements are in H and which are not.

31Thus P_{K} = ∑_{(b_{1},...,b_{m})∈G^{m}} |Ψ(K, {b_{i}})⟩⟨Ψ(K, {b_{i}})|

We bound this probability of success. Let |Ψ_{0}⟩ = |Ψ⟩. For 1 ≤ i ≤ |G|, define the unnormalized states

(87)  |Ψ_{i}⟩ = \{ \begin{matrix}P_{⟨g_{i}⟩}|Ψ_{i−1}⟩ & if g_{i} ∈ H \\ P_{⟨g_{i}⟩}^{⊥}|Ψ_{i−1}⟩ & if g_{i} ∉ H \end{matrix}

By induction and the definition of the probabilities, ⟨Ψ_{i}|Ψ_{i}⟩ equals the probability that the algorithm given above answers correctly whether g_{j} ∈ H for all 1 ≤ j ≤ i. Now for all 0 ≤ i ≤ |G| let |E_{i}⟩ = |Ψ⟩ − |Ψ_{i}⟩ denote the error between the original state and the desired state after testing ⟨g_{i}⟩.

Since |Ψ_{|G|}⟩ = |Ψ⟩ − |E_{|G|}⟩, using ⟨E_{|G|}|E_{|G|}⟩ ≤ \frac{|G|^{2}}{2^{m}} by lemma 5.40 and the triangle inequality gives that the probability for correctly determining all the elements of H is bounded below by ⟨Ψ_{|G|}|Ψ_{|G|}⟩ ≥ 1 − \frac{2|G|}{2^{m/2}} .

By choosing m = ⌈4 log |G| + 2⌉ the main theorem follows directly. □

Lemma 5.39. Use the notation above. Let K ≤ G. If K ≰ H then ⟨Ψ|P_{K}|Ψ⟩ ≤ \frac{1}{2^{m}}. If K ≤ H then ⟨Ψ|P_{K}|Ψ⟩ = 1.

Proof. Let |H ∩ K| = d. Note that for all g_{1}, g_{2} ∈ G we have |g_{1}H ∩ g_{2}K| = d or |g_{1}H ∩ g_{2}K| = 0. This implies that if |g_{1}H ∩ g_{2}K| = d then ⟨g_{1}H|g_{2}K⟩ = d/\sqrt{|H||K|}. Therefore for any subset \{b_{1}, …, b_{m}\} ⊆ G

(88) ⟨Ψ|Ψ(K, \{b_{i}\})⟩ = \{ \begin{matrix}(\frac{d}{\sqrt{|H||K|}})m & if |a_{i}H ∩ b_{i}K| = d for i = 1, 2, …, m \\ 0 & otherwise \end{matrix}

There exist exactly (|H|/d)^{m} vectors of the form |Ψ(K, {b_{i}})⟩ with ⟨Ψ|Ψ(K, {b_{i}})⟩ nonzero. Hence ⟨Ψ|P_{K}|Ψ⟩ = (\frac{|H|}{d})^{m} (\frac{d^{2}}{|H||K|})^{m} = (\frac{d}{|K|})^{m}. If K ≰ H then d/|K| ≤ 1/2 and if K ≤ H then d = K. □

Lemma 5.40. For all 0 ≤ i ≤ |G| we have ⟨E_{i}|E_{i}⟩ ≤ \frac{i^{2}}{2^{m}}.

Proof. Proof by induction on i. Since |Ψ_{0}⟩ = |Ψ⟩, by definition |E_{0}⟩ = 0. Now suppose ⟨E_{i}|E_{i}⟩ ≤ \frac{i^{2}}{2^{m}}. If g_{i+1} ∈ H, then |Ψ_{i+1}⟩ = P_{⟨g_{i+1}⟩} (|Ψ⟩ − |E_{i}⟩) = |Ψ⟩ − P_{⟨g_{i+1}⟩}|E_{i}⟩. Hence ⟨E_{i+1}|E_{i+1}⟩ ≤ ⟨E_{i}|E_{i}⟩ ≤ \frac{i^{2}}{2^{m}}. If g_{i+1} ∉ H, then |Ψ_{i+1}⟩ = P_{⟨g_{i+1}⟩}^{⊥} (|Ψ⟩ − |E_{i}⟩) = |Ψ⟩ − P_{⟨g_{i+1}⟩}|Ψ⟩ − P_{⟨g_{i+1}⟩}^{⊥}|E_{i}⟩. By lemma 5.39 we then have

⟨E_{i+1}|E_{i+1}⟩ = ⟨Ψ|P_{⟨g_{i}⟩}|Ψ⟩ + ⟨E_{i}|E_{i}⟩ ≤ \frac{1}{2^{m}} + \frac{i^{2}}{2^{m}} ≤ \frac{(i+1)^{2}}{2^{m}}. □

6. Conclusion

In conclusion, we have shown in great detail how to find hidden subgroups in any finite abelian group. This was shown to be efficient using a quantum computer, and is the basis for Shor’s factoring algorithm, as well as many other exponentially faster quantum algorithms. The key ingredient was Fourier sampling - that is, doing a quantum Fourier transform on a state encoding the hidden subgroup, and then measuring (sampling) the resulting state to gather information used to compute the hidden subgroup generators.

Also, we described the nonabelian case of the HSP, using representation theory to define the Fourier transform over arbitrary finite groups, and then mimicking the abelian case in an attempt to solve the HSP efficiently for any finite group.

However this case is much harder, and only partial results are known, many of which we listed.

The main open problem in the field is finding an efficient quantum algorithm for the symmetric group S_{n}, which would yield an elusive (for over 30 years) efficient algorithm for determining graph isomorphism. However it seems that quantum Fourier sampling may not be up to the task since there are many negative results. Yet there is hope that a clever basis choice for the irreducible representations might turn this around. A second possibility, also seemingly remote, is finding a new quantum algorithm which does the trick, avoiding Fourier sampling completely.

6.1. Other Quantum Algorithms. There are many other areas where quantum algorithms are better than classical ones. One of the earliest algorithms was Grover’s searching algorithm [54], which reduces the classical complexity of searching an unordered list of N items from O(N) to a provably best quantum Θ(\sqrt{N}) oracle queries^{32}. See also [21]. This was exploited by [106] to make a quantum string matching algorithm much faster the best classical algorithms given in [80, 22].

Other quantum algorithms are found in [1, 24, 40, 58, 60, 61, 62, 70, 73, 124]. More quantum algorithm overviews are in [7, 17, 32, 50, 86, 99, 116]. Continuous variable algorithms are considered in [85, 104, 105]. A good point to start learning quantum error correction is [26].

Another interesting direction is taken by Orús, Latorre, and Martín-Delgado in [101, 102] where the authors notice an invariant of efficient quantum algorithms labelled “majorization,” which they use to seek new algorithms.

A final direction is adiabatic quantum computation [123], another quantum computation computing model that may be physically realizable. It has recently been shown to be equivalent to the standard qubit model [3], but provides another viewpoint for quantum computation.

32Many authors claim O(\sqrt{N}) is the algorithm time complexity. A careful look shows O(\sqrt{N} log N) is a more reasonable time complexity.

These appendices contain results used above.

Appendix A. The Cyclic Quantum Fourier Transform over ℤ_{N}

Here we give details on the cyclic QFT over ℤ_{2^{n}} and over ℤ_{N} for N odd.

A.1. The Quantum Fourier Transform over ℤ_{2^{n}}. This section follows Coppersmith [35]. Since we already showed how to do the QFT over ℤ_{2^{n}} in section 3.4.2, we only have to cover the approximate QFT. The main result is

Theorem A.1. Given an ϵ > 0 and a positive integer n, let N = 2^{n}. Then there is a quantum circuit approximating the Fourier transform over ℤ_{N} using O(log N(log log N +log(1/ϵ))) 2-qubit operations. The approximated quantum state |ϕ⟩ differs from the true Fourier transformed state |ψ⟩ by ∥ |ϕ⟩ − |ψ⟩ ∥ < ϵ.

Proof. Let n be a positive integer. Let a, c be n-bit integers. The binary representations of a and c are

(89)  a = ∑_{i=0}^{n−1} a_{i}2^{i}, c = ∑_{i=0}^{n−1} c_{i}2^{i}.

Let X, Y be arrays of size 2^{n} indexed by a or c. Let ω = ω_{2^{n}} = exp(2πi/2^{n}) be the standard 2^{n} root of unity.

The Fourier transform is defined as

(90)  Y_{c} = \frac{1}{\sqrt{2^{n}}} ∑_{a} X_{a}ω^{ac} = \frac{1}{\sqrt{2^{n}}} ∑_{a} X_{a} exp (\frac{2π}{2^{n}} ac) ,

or, in binary notation,

(91)  Y_{c} = \frac{1}{\sqrt{2^{n}}} ∑_{a} X_{a} exp (\frac{2π}{2^{n}} ∑_{j,k=0}^{n−1} a_{j}c_{k}2^{j+k}) .

Whenever j + k ≥ n, ω^{2^{j+k}} = 1, so we drop those terms, giving the Fast Fourier Transform (FFT)

(FFT) Y_{c} = \frac{1}{\sqrt{2^{n}}} ∑_{a} X_{a} exp (\frac{2π}{2^{n}} ∑_{\begin{matrix}0≤j,k≤n−1 \\ j+k≤n−1 \end{matrix}} a_{j}c_{k}2^{j+k}) .

Now we approximate. Instead of the summation range having a 0 ≤ j + k ≤ n − 1 bound, we parameterize on a positive integer m < n and bound by n−m ≤ j +k ≤ n − 1, giving the Approximate Fast Fourier Transform (AFFT_{m}):

(AFFT_{m}) Y_{c} = \frac{1}{\sqrt{2^{n}}} ∑_{a} X_{a} exp (\frac{2π}{2^{n}} ∑_{\begin{matrix}0≤j,k≤n−1 \\ n−m≤j+k≤n−1 \end{matrix}} a_{j}c_{k}2^{j+k}) .

The argument of “exp” in the AFFT differs from that in the FFT by

(92)  \frac{2πi}{2^{n}} ∑_{j+k<n−m} a_{j}c_{k}2^{j+k},

and is bounded in magnitude by

|\frac{2πi}{2^{n}} ∑_{\begin{matrix}0≤j,k≤n−1 \\ j+k<n−m \end{matrix}} a_{j}c_{k}2^{j+k}| ≤ \frac{2π}{2^{n}} ∑_{0≤j<n−m} 2^{j} ∑_{0≤k<n−m−j} 2^{k}

= \frac{2π}{2^{n}} ∑_{0≤j<n−m} 2^{j} (2^{n−m−j} − 1)

= \frac{2π}{2^{n}} ((n − m)2^{n−m} − 2^{n−m} + 1)
≤ \frac{2π}{2^{n}} n2^{n−m}
= 2πn2^{−m}.

So the matrix entries of the AFFT differ from the FFT by a multiplicative factor of exp(iδ), where |δ| ≤ 2πn2^{−m}. Let this error be exp(δ_{j,k}) in the (j, k) entry. From arc length on a circle, we have |1 − e^{iδ}| ≤ |δ|.

To compute the error between the quantum states resulting from the FFT and AFFT, compute for any state |ψ⟩ = ∑_{j} a_{j}|j⟩

(93) ∥(FFT − AFFT_{m})|ψ⟩∥^{2} = ∑_{k=0}^{N−1} |\frac{1}{\sqrt{N}} ∑_{j=0}^{N−1} ω_{N}^{jk}a_{j}(1 − exp(δ_{j,k}))|^{2}

(94)  ≤ (2πn2^{−m})^{2} ∑_{k=0}^{N−1} |\frac{1}{\sqrt{N}} ∑_{j=0}^{N−1} ω_{N}^{jk}a_{j}|^{2}
(95)  = (2πn2^{−m})^{2} ∥FFT|ψ⟩∥^{2}
(96)  = (2πn2^{−m})^{2} · 1

Thus for any ϵ > 0, taking m ≥ log(2π) + log n + log(1/ϵ) gives that

(97)  ∥(FFT − AFFT_{m})|ψ⟩∥ < ϵ

Now we show how to compute the AFFT efficiently, similar to the method in section 3.4.2. Let Q^{(J,K)} be the operation that multiplies the amplitude of those states with a 1 in positions J and K by a factor of ω^{2^{n−1−K−J}}. This is similar to the R_{k}^{(a,b)} defined for the QFT earlier. Let H^{(J)} be the operation of applying the

Hadamard matrix \frac{1}{\sqrt{2}} (\begin{matrix}1 & 1 \\ 1 & −1 \end{matrix}) to qubit J. Then check that the operation

(98)  H^{(0)}Q^{(0,1)}Q^{(0,2)} … Q^{(0,n−1)}H^{(1)}Q^{(1,2)}Q^{(1,3)} … Q^{n−2,n−1}H^{(n−1)}

performs the QFT as earlier. To perform the AFFT we drop those Q^{(J,K)} with K ≥ J + m, so it requires about nm 2-qubit operations. Taking m = O(log n + log(1/ϵ)) to bound the error as required, we obtain the complexity bound. □

A.2. The Quantum Fourier Transform over ℤ_{N}, N Odd. This section gives an algorithm to approximate the QFT over ℤ_{N} efficiently. The algorithm is from the Hales thesis [55] and the paper by Hallgren et .al [57] , but their proofs are incorrect. This section gives the proof from Lomont [88]. The end result is a proof of the correctness of their algorithm, with concrete bounds suitable for quantum simulation instead of the asymptotic bounds listed in their papers. The final result is theorem A.17. The general idea of the algorithm is to make many copies of the initial state vector and perform a 2^{n} style QFT for a large value, and extract from this state period information for the original odd N. The proof requires a lot tedious work; it is more instructive to work through the algorithm until the general idea is clear.

A.2.1. Notation and Basic Facts. We fix three integers: an odd integer N ≥ 3, L ≥ 2 a power of 2, and M ≥ LN a power of 2. This gives (M, N) = 1, which we need later.

Some notation and facts to clarify the presentation: • \sqrt{−1} will be written explicitly, as i will always denote an index.

• For an integer n > 1, let ω_{n} = e^{2π\sqrt{−1}/n} denote a primitive n^{th} root of unity.

• Fact: |1 − e^{θ\sqrt{−1}}| ≤ |θ| as can be seen from arc length on the unit circle.

If −π ≤ θ ≤ π we also^{33} have |\frac{θ}{2} | ≤ |1 − e^{θ\sqrt{−1}}|. Thus for real values α we

have |1 − ω_{M}^{α}| ≤ |\frac{2πα}{M} |, etc.

• log n denotes log base 2, while ln n is the natural log. Since M and L are powers of two, ⌈log M⌉ = ⌊log M⌋ = ⌊log M⌉ = log M, and similarly for L, but we often leave the symbols to emphasize expressions are integral.

• For a real number x, ⌈x⌉ is the smallest integer greater than or equal to x, ⌊x⌋ is the largest integer less than or equal to x, and ⌊x⌉ is the nearest integer, with ties rounding up^{34}. We often use the three relations:

x − \frac{1}{2} ≤ ⌊x⌉ ≤ x + \frac{1}{2}
x − 1 < ⌊x⌋ ≤ x
x ≤ ⌈x⌉ < x + 1

• Indices: i and s will be indices from 0, 1, …, N − 1. j will index from 0, 1, …, L − 1. k will index from 0, 1, …, M − 1. a and b will be arbitrary indices. t will index from a set C_{s}, defined in definition A.3 below.

• Given i ∈ \{0, 1, …, N − 1\}, let i′ = ⌊\frac{M}{N} i⌉ denote the nearest integer to \frac{M}{N} i with ties broken as above. Similarly for s and s′. Note 0 ≤ i′ ≤ M − 1.

• For a real number x and positive real number n, let x mod n denote the real number y such that 0 ≤ y < n and y = x + mn for an integer m. Note that we do not think of x mod n as an equivalence class, but as a real number in [0, n).

• |u⟩ and |v⟩ are vectors in spaces defined later, and given a vector |u⟩ denote its coefficients relative to the standard (orthonormal) basis {|0⟩, |1⟩, …, |n− 1⟩} by u_{0}, u_{1}, …, u_{n−1}, etc.

• For a real number x, let

|x|_{M} = \begin{cases}x mod M & if & 0 ≤ (x mod M) ≤ \frac{M}{2} \\ −x mod M & otherwise \end{cases} Thus 0 ≤ |x|_{M} ≤ \frac{M}{2} . Properties of this function are easiest to see by noting it is a sawtooth function, with period M, and height M/2.

33This range can be extended slightly.

34We could break ties arbitrarily with the same results.

• For an integer s set δ_{s} = ⌊\frac{M}{N} s⌉ − \frac{M}{N} s. Then |δ_{s}| ≤ \frac{1}{2}.

• The (unitary) Fourier transform over a cyclic group of order N is denoted F_{N}. Thus if |u⟩ = ∑_{i=0}^{N−1} u_{i}|i⟩, then F_{N}|u⟩ = \frac{1}{\sqrt{N}} ∑_{i,s=0}^{N−1} u_{i}ω_{N}^{is}|s⟩. We write |û⟩ = F_{N}|u⟩, with coefficients û_{i}.

• ∑_{i=0}^{N−1} |u_{i}|^{2} = 1 implies ∑_{i} |u_{i}| ≤ \sqrt{N}.

We define sets of integers which will play an important role:

Definition A.2. For i = 0, 1, …, N − 1, let (i) denote the set of integers in the open interval (i′ − \frac{M}{2N} + \frac{1}{2}, i′ + \frac{M}{2N} − \frac{1}{2}) taken mod M. Recall i′ = ⌊\frac{M}{N} i⌉.

The second definition we make precise is a division and remainder operation:

Definition A.3. Given M, N as above. Set α = ⌊\frac{M}{2N} + \frac{1}{2}⌋, and β = ⌈\frac{M}{2N} − \frac{3}{2}⌉. We define the map Δ : {0, 1, …, M −1} → {0, 1, …, N −1}×{−α, −α+1, …, α}, as follows: for any k ∈ {0, 1, …, M − 1}, let k ⟶^{Δ} (s, t), via

k′ = ⌊k \frac{N}{M} ⌉
t = k − ⌊k′ \frac{M}{N} ⌉
s = k′ mod N

We extend this definition to a transform of basis elements |k⟩ via

Δ|k⟩ = |s⟩|t + α⟩

and extend to all vectors by linearity.

Finally, from the image of Δ, define C_{s} = { t | (s, t) ∈ Image Δ} to be those

values of t appearing for a fixed s. Thus ∑_{k=0}^{M−1} |k⟩ ⟶^{Δ} ∑_{s=0}^{N−1} ∑_{t∈C_{s}} |s⟩|t + α⟩.

We will show the integers {−β, …, β} ⊆ C_{s} ⊆ {−α, …, α} for all s, which is why we defined β with the Δ definition. α and β remain fixed throughout the paper.

For the proofs to work, we need that the sets (i) are disjoint and have the same cardinality. Note also that the mod M condition gives M − 1, 0 ∈ (0) when M > 3N. We now show that the sets defined here have the required properties:

Lemma A.4. For i_{1} ≠ i_{2} ∈ {0, 1, …, N − 1},

(99)  |(i_{1})| = |(i_{2})|
(100)  (i_{1}) ⋂(i_{2}) = ∅

Proof. Each set is defined using an interval of constant width, centered at an integer, so the sets will have the same cardinality. To show disjointness, for any integer a, take the rightmost bound R_{a} = ⌊\frac{M}{N} a⌉ + \frac{M}{2N} − \frac{1}{2} of an interval and compare it to the leftmost bound L_{a+1} = ⌊\frac{M}{N} (a + 1)⌉ − \frac{M}{2N} + \frac{1}{2} of the next interval:

(101)  L_{a+1} − R_{a} = ⌊\frac{M}{N} (a + 1)⌉ − ⌊\frac{M}{N} a⌉ − \frac{M}{N} + 1
(102)  ≥ (\frac{M}{N} (a + 1) − \frac{1}{2}) − (\frac{M}{N} a + \frac{1}{2}) − \frac{M}{N} + 1
(103)  = 0

giving that the open intervals are disjoint. Thus taking the integers in the intervals mod M remains disjoint (which requires i_{1}, i_{2} ≤ N − 1). □

Note the image of Δ is not a cartesian product; the values t assumes depend on s, otherwise we would have that M is a multiple of N. In other words, the cardinality of C_{s} depends on s, with bounds given in the following lemma, where we show that our definition works and list some properties:

Lemma A.5. Using the notation from definition A.3, 1) the map Δ is well defined, and a bijection with its image,

2) α = β + 1,

3) the sets of integers satisfy {−β, …, β} ⊆ C_{s} ⊆ {−α, …, α} for all s ∈ {0, 1, …, N − 1}.

Proof. Given a k in {0, 1, …, M − 1}, let Δ(k) = (s, t). Clearly 0 ≤ s ≤ N − 1. Set α = ⌊\frac{M}{2N} + \frac{1}{2}⌋. To check that −α ≤ t ≤ α, note

(104)  \frac{N}{M} k − \frac{1}{2} ≤ k′ ≤ \frac{N}{M} k + \frac{1}{2}

giving

(105)  \frac{M}{2N} + \frac{1}{2} ≥ t = k − ⌊\frac{M}{N} k′⌉ ≥ − (\frac{M}{2N} + \frac{1}{2})

and t integral allows the rounding operation. Thus the definition makes sense.

Next we check that both forms of Δ in the definition are bijections. Suppose k_{1} ≠ k_{2} are both in {0, 1, …, M − 1}, with images Δ(k_{r}) = (s_{r}, t_{r}), r = 1, 2. Let k′_{r} = ⌊\frac{N}{M} k_{r}⌉ , r = 1, 2. Note 0 ≤ k′_{r} ≤ N.

Assume (s_{1}, t_{1}) = (s_{2}, t_{2}). If k′_{1} = k′_{2}, then

(106)  t_{1} = k_{1} − ⌊\frac{M}{N} k′_{1}⌉ = k_{1} − ⌊\frac{M}{N} k′_{2}⌉

≠ k_{2} − ⌊\frac{M}{N} k′_{2}⌉ = t_{2} (107)

a contradiction. So we are left with the case k′_{1} ≠ k′_{2}. In order for s_{1} = s_{2} we have (without loss of generality) k′_{1} = 0, k′_{2} = N. But then t_{1} = k_{1} ≥ 0 and t_{2} = k_{2} − M ≤ M − 1 − M = −1, a contradiction. Thus Δ in the first sense is a bijection.

The second interpretation follows easily, since −α ≤ t ≤ α gives 0 ≤ t + α ≤ 2α. So the second register needs to have a basis with at least 2α + 1 elements, which causes the number of qubits needed^{35} to implement the algorithm to be ⌈log M⌉+2 instead of ⌈log M⌉.

35This is proven in theorem A.17.

To see α = β + 1, bound α − β using the methods above, and^{36} one obtains 2 > α − β > 0.

All integers between ⌊\frac{M}{N} (s + 1)⌉ and ⌊\frac{M}{N} s⌉ inclusive must be of the form t_{1} + ⌊\frac{M}{N} s⌉ for t_{1} ∈ C_{s} or of the form t_{2} + ⌊\frac{M}{N} (s + 1)⌉ for t_{2} ∈ C_{s+1}. This range contains ⌊\frac{M}{N} (s + 1)⌉ − ⌊\frac{M}{N} s⌉ + 1 ≥ \frac{M}{N} integers, and at most α + 1 of these are of the form t_{2} + ⌊\frac{M}{N} (s + 1)⌉ with t_{2} ∈ C_{s+1}. This leaves at least ⌈\frac{M}{N} ⌉ − α ≥ \frac{M}{2N} − \frac{3}{2} that have to be of the form t_{1} + ⌊\frac{M}{N} s⌉ with t_{1} ∈ C_{s}, implying β ∈ C_{s}. Similar arguments give ±β ∈ C_{s}, thus {−β, …, β} ⊆ C_{s} ⊆ {−α, …, α} for all s. □

Δ is efficient to implement as a quantum operation, since it is efficient classically [29, Chapter 4]. Finally we note that Δ, being a bijection, can be extended to a permutation of basis vectors |k⟩, thus can be considered an efficiently implementable unitary operation.

We define some vectors we will need. For i ∈ {0, 1, …, N − 1} define

|A^{i}⟩ = F_{M}F_{LN}^{−1}|Li⟩
= \frac{1}{\sqrt{LMN}} ∑_{k=0}^{M−1} ∑_{a=0}^{LN−1} ω_{N}^{−ai}ω_{M}^{ak}|k⟩
|B^{i}⟩ = |A^{i}⟩ restricted to integers in the set (i)
= ∑_{b∈(i)} A_{b}^{i}|b⟩

= \frac{1}{\sqrt{LMN}} ∑_{b∈(i)} ∑_{a=0}^{LN−1} ω_{N}^{−ai}ω_{M}^{ab}|b⟩
|T^{i}⟩ = |A^{i}⟩ restricted to integers outside the set (i)
= ∑_{b∉(i)} A_{b}^{i}|b⟩
= |A^{i}⟩ − |B^{i}⟩
= \frac{1}{\sqrt{LMN}} ∑_{b∉(i)} ∑_{a=0}^{LN−1} ω_{N}^{−ai}ω_{M}^{ab}|b⟩

Think A^{i} for actual values, B^{i} for bump functions, and T^{i} for tail functions. Note that the coefficients B_{b}^{i} and T_{b}^{i} are just A_{b}^{i} for b in the proper ranges.

We also define three equivalent shifted versions of |B^{0}⟩. Note that to make these definitions equivalent we require the sets (i) to have the same cardinality. Let |S^{i}⟩ = ∑_{b∈(0)} B_{b}^{0}|b + i′⟩ = ∑_{b∈(0)} A_{b}^{0}|b + i′⟩ = ∑_{b∈(i)} A_{b−i′}^{0}|b⟩, where each b ± i′ expression is taken mod M. The |S^{i}⟩ have disjoint support, which follows from lemma A.4, and will be important for proving theorem A.14.

A.2.2. The Algorithm. The algorithm takes a unit vector (quantum state) |u⟩ on ⌈log N⌉ qubits^{37}, does a Fourier transform F_{L}, L a power of two, on another register containing |0⟩ with ⌈log M⌉ − ⌈log N⌉ + 2 qubits, to create^{38} a superposition, and then reindexes the basis to create L (normalized) copies of the coefficients of |u⟩, resulting in |u_{L}⟩. Then another power of two Fourier transform F_{M} is applied. The division Δ results in a vector very close to the desired output F_{N}|u⟩ in the first register, with garbage in the second register (with some slight entanglement). The point of this paper is to show how close the output is to this tensor product. We use ⌈log M⌉ + 2 qubits, viewed in two ways: as a single register |k⟩, or as a ⌈log N⌉- qubit first register, with the remaining qubits in the second register, written |s⟩|t⟩. We note that merely ⌈log M⌉ qubits may not be enough qubits to hold some of the intermediate results. The algorithm is:

36(M, N) = 1 is used to get the strict inequalities.

37Recall logs are base 2.

38Note it may be more efficient to apply the Hadamard operator H to each qubit in |0⟩.

A.2.3. The Odd Cyclic QFT Algorithm.

(108) |u⟩|0⟩ ⟶^{F_{L}}  \frac{1}{\sqrt{L}} ∑_{i=0}^{N−1} ∑_{j=0}^{L−1} u_{i}|i⟩|j⟩

(109)  ⟶^{multiply} \frac{1}{\sqrt{L}} ∑_{i,j} u_{i}|i + jN⟩
(110)  =  |u_{L}⟩
(111)  ⟶^{F_{M}}  \frac{1}{\sqrt{LM}} ∑_{i,j} ∑_{k=0}^{M−1} u_{i}ω_{M}^{(i+jN)k}|k⟩

(112)  ⟶^{Δ}  \frac{1}{\sqrt{LM}} ∑_{i,j} u_{i} ∑_{s=0}^{N−1} ∑_{t∈C_{s}} ω_{M}^{(i+jN)(t+⌊\frac{M}{N} s⌉)}|s⟩|t + α⟩

(113)  =  \frac{1}{\sqrt{N}} ∑_{i,s=0}^{N−1} u_{i}ω_{N}^{is}|s⟩\sqrt{\frac{N}{LM}} ∑_{t∈C_{s}} ∑_{j=0}^{L−1} ω_{M}^{(i+jN)(t+δ_{s})}|t + α⟩
(114)  =  |v⟩

|u_{L}⟩ is the vector that is L copies of the coefficients from |u⟩, normalized. |v⟩ is the algorithm output.

Notice that F_{N}|u⟩ appears in the output in line 113, but the rest is unfortunately dependent on s and i. However the dependence is small: if C_{s} were the same for all s, if the δ_{s}, which are bounded in magnitude by \frac{1}{2}, were actually zero, and if the i dependence were dropped, then the output would leave F_{N}|u⟩ in the first register. The paper shows this is approximately true, and quantifies the error.

A.2.4. Initial Bounds. We need many bounds to reach the final theorem, which we now begin proving.

Lemma A.6. For integers N > 2, M ≥ 2N, and any i ∈ {0, 1, …, N − 1}, k ∈ {0, 1, …, M − 1}, with k ∉ (i), we have

(115)  |k − \frac{M}{N} i|_{M} ≥ \frac{M}{2N} − 1

Proof. The sets (i) are disjoint, so we do two cases. If i = 0, then k ∉ (0) implies

(116)  \frac{M}{2N} − \frac{1}{2} ≤ k ≤ M − \frac{M}{2N} + \frac{1}{2}

from which it follows that

(117)  |k − \frac{M}{N} 0|_{M} ≥ \frac{M}{2N} − \frac{1}{2} > \frac{M}{2N} − 1

If i ≠ 0, then either k is less than the integers in (i) or greater than the integers in (i), giving two subcases. Subcase 1:

(118)  0 ≤ k ≤ ⌊\frac{M}{N} i⌉ − \frac{M}{2N} + \frac{1}{2} ≤ \frac{M}{N} i − \frac{M}{2N} + 1

implying

(119)  \frac{M}{2N} − 1 ≤ \frac{M}{N} i − k ≤ \frac{M}{N} i ≤ M − \frac{M}{N}

which gives the bound. Subcase 2 is then

(120)  \frac{M}{N} i + \frac{M}{2N} − 1 ≤ ⌊\frac{M}{N} i⌉ + \frac{M}{2N} − \frac{1}{2} ≤ k ≤ M − 1

which implies

(121)  \frac{M}{2N} − 1 ≤ k − \frac{M}{N} i ≤ M − 1 − \frac{M}{N} i

giving the bound and the proof. □

We now bound many of the |A^{i}⟩ coefficients.

Lemma A.7. For k ∈ \{0, 1, …, M − 1\} and i ∈ \{0, 1, …, N − 1\}, with \frac{k}{M} − \frac{i}{N} not an integer, then

(122)  |A_{k}^{i}| ≤ \sqrt{\frac{M}{LN}} \frac{2}{π |k − \frac{M}{N} i|_{M}}

Proof. We rewrite from the definition

(123)  A_{k}^{i} = \frac{1}{\sqrt{LMN}} ∑_{a=0}^{LN−1} ω_{M}^{a(k− \frac{M}{N} i)}

(124)

which is a geometric series. By hypothesis, ω_{M}^{(k− \frac{M}{N} i)} ≠ 1, so we can sum as^{39}

(125)  |A_{k}^{i}| = \frac{1}{\sqrt{LMN}} |\frac{1 − ω_{M}^{LN(k− \frac{M}{N} i)}}{1 − ω_{M}^{(k− \frac{M}{N} i)}} |

The numerator is bounded above by 2, and the denominator satisfies

(126)  |1 − ω_{M}^{(k− \frac{M}{N} i)}| = |1 − ω_{M}^{|k− \frac{M}{N} i|_{M}} |

(127)  ≥ \frac{π |k − \frac{M}{N} i|_{M}}{M}

39Without this requirement, the sum would be LN, much different than the claimed sum. The hypotheses avoid the resulting divide by zero.

These together give

(128)  |A_{k}^{i}| ≤ \sqrt{\frac{M}{LN}} \frac{2}{π |k − \frac{M}{N} i|_{M}}
□

Note our initial requirement that (M, N) = 1 is strong enough to satisfy the non-integral hypothesis in lemma A.7, except for the case i = k = 0, which we will avoid.

Next we bound a sum of these terms. We fix γ = \frac{1}{2} − \frac{N}{M} for the rest of this paper.

Lemma A.8. Given integers N > 2 and M > 2N, with N odd. Let γ = \frac{1}{2} − \frac{N}{M}. For a fixed integer k ∈ {0, 1, …, M − 1},

(129)  ∑_{\begin{matrix}i=0 \\ k∉(i) \end{matrix}}^{N−1} \frac{1}{|k − \frac{M}{N} i|_{M}} ≤ \frac{2N}{M} (\frac{1}{γ} + ln |\frac{N − 1}{2γ} + 1| )

Proof. The minimum value of the denominator is at least \frac{M}{2N} − 1 by lemma A.6, and the rest are spaced out by \frac{M}{N}, but can occur twice^{40} since the denominator is a sawtooth function going over one period, giving that

(130)  ∑_{\begin{matrix}i=0 \\ k∉(i) \end{matrix}}^{N−1} \frac{1}{|k − \frac{M}{N} i|_{M}} ≤ 2 ∑_{a=0}^{\frac{N−1}{2}} \frac{1}{\frac{M}{2N} − 1 + \frac{M}{N} a}

(131)  = \frac{2N}{M} (\frac{1}{γ} + ∑_{a=1}^{\frac{N−1}{2}} \frac{1}{γ + a})

(132)  ≤ \frac{2N}{M} (\frac{1}{γ} + ∫_{0}^{(N−1)/2} \frac{1}{x + γ} dx)

(133)  = \frac{2N}{M} (\frac{1}{γ} + ln |\frac{N − 1}{2γ} + 1| )
□

The generality of the above lemma would be useful where physically adding more qubits than necessary would be costly, since the lemma lets the bound tighten as \frac{N}{M} decreases. However the following corollary is what we will use in the final theorem.

Corollary A.9. Given integers N ≥ 13 and M ≥ 16N, with N odd. For a fixed value k ∈ {0, 1, …, M − 1},

(134)  ∑_{\begin{matrix}i=0 \\ k∉(i) \end{matrix}}^{N−1} \frac{1}{|k − \frac{M}{N} i|_{M}} ≤ \frac{4N ln N}{M}

40Both [55] and [57] appear to overlook this fact.

Proof. Using lemma A.8, M ≥ 16N gives \frac{1}{γ} ≤ \frac{16}{7} and

(135)  \frac{1}{γ} + ln |\frac{N − 1}{2γ} + 1| ≤ \frac{16}{7} + ln |\frac{8(N − 1)}{7} + 1|
(136)  = ln (e^{\frac{16}{7}} (\frac{8(N − 1)}{7} + 1))
(137)  ≤ ln (\frac{8}{7} e^{\frac{16}{7}} N)
(138)  ≤ 2 ln N

where the last step required N ≥ (\frac{8}{7} e^{\frac{16}{7}} ) > 11.2. The corollary follows. □

Next we prove a bound on a sum of the above terms, weighted with a real unit vector. This will lead to a bound on the tails ∥∑_{i} û_{i}|T^{i}⟩∥.

Lemma A.10. Given integers N ≥ 13 and M ≥ 16N, with N odd. For any unit vector x ∈ ℝ^{N}

(139)  ∑_{k=0}^{M−1} | ∑_{\begin{matrix}i=0 \\ k∉(i) \end{matrix}}^{N−1} \frac{x_{i}}{|k − \frac{M}{N} i|_{M}} |^{2} ≤ \frac{22N ln^{2} N}{M} + \frac{32N^{3}}{M^{2}}

Proof. We split the expression into three parts, the first of which we can bound using methods from [55] and [57], and the other two terms we bound separately.

Using the Δ operator from definition A.3, along with the values α and β defined there, and using lemma A.5, we can rewrite each k with k = t+⌊\frac{M}{N} k′⌉ = t+ \frac{M}{N} k′+δ_{s}. Since s differs from k′ by a multiple of N, and the |x|_{M} function has period M, in |\frac{M}{N} (k′ − i) + t + δ_{s}|_{M} we can replace k′ with s. Rewrite the left hand side of inequality 139 as

(140)  ∑_{k=0}^{M−1} | ∑_{\begin{matrix}i=0 \\ k∉(i) \end{matrix}}^{N−1} \frac{x_{i}}{|k − \frac{M}{N} i|_{M}} |^{2} = ∑_{s=0}^{N−1} ∑_{t∈C_{s}} | ∑_{\begin{matrix}i=0 \\ s≠i \end{matrix}}^{N−1} \frac{x_{i}}{|\frac{M}{N} (s − i) + t + δ_{s}|_{M}} |^{2}

Letting Δk = (s, t), note that k ∉ (i) if and only if s ≠ i, which can be shown from the definitions and the rounding rules used earlier. To simplify notation, write q_{i,s}^{t} = \frac{M}{N} (s − i) + t + δ_{s}. We have not changed the values of the denominators, so |q_{i,s}^{t}|_{M} ≥ \frac{M}{2N} − 1 by lemma A.6 for all i, (s, t) in this proof.

We want to swap the s and t sums, but we need to remove the t dependence on s. Again using lemma A.5, we can split the expression into the three terms:

∑_{t=−β}^{β} ∑_{s=0}^{N−1} | ∑_{\begin{matrix}i=0 \\ s≠i \end{matrix}}^{N−1} \frac{x_{i}}{|q_{i,s}^{t}|_{M}} |^{2} (141)

+ ∑_{s with α∈C_{s}} | ∑_{\begin{matrix}i=0 \\ s≠i \end{matrix}}^{N−1} \frac{x_{i}}{|q_{i,s}^{α}|_{M}} |^{2} (142)

+ ∑_{s with −α∈C_{s}} | ∑_{\begin{matrix}i=0 \\ s≠i \end{matrix}}^{N−1} \frac{x_{i}}{|q_{i,s}^{−α}|_{M}} |^{2} (143)

Next we bound the first term 141. For a unit vector x and fixed t we rewrite the s, i sum as the norm of a square matrix P_{t} acting on x, so that the sum over s and i becomes

(144)  ∥P_{t}x∥^{2} = ∑_{s=0}^{N−1} | ∑_{\begin{matrix}i=0 \\ s≠i \end{matrix}}^{N−1} \frac{x_{i}}{|q_{i,s}^{t}|_{M}} |^{2}

We also define similarly to each P_{t} a matrix Q_{t} which is the same except for minor modifications to the denominator:

(145)  ∥Q_{t}x∥^{2} = ∑_{s=0}^{N−1} | ∑_{\begin{matrix}i=0 \\ s≠i \end{matrix}}^{N−1} \frac{x_{i}}{|q_{i,s}^{t} − δ_{s}|_{M}} |^{2}

Note this matrix is circulant^{41}, since each entry in the matrix only depends on s−i. Also each entry is nonnegative^{42}. Thus the expression is maximized by the vector y = \frac{1}{\sqrt{N}} (1, 1, …, 1) as shown in each of [55], [57], and [65]. Now we relate these matrix expressions. Recall |q_{i,s}^{t}|_{M} ≥ \frac{M}{2N} − 1 and |δ_{s}| ≤ \frac{1}{2}. Set λ = \frac{N}{M−2N}. Then we find lower and upper bounds

1 − λ = 1 − \frac{1}{2(\frac{M}{2N} − 1)} ≤ \frac{|q_{i,s}^{t}|_{M} − \frac{1}{2}}{|q_{i,s}^{t}|_{M}} ≤ \begin{matrix}|q_{i,s}^{t} − δ_{s}| & M \\ |q_{i,s}^{t}| & M \end{matrix} (146)

and

\begin{matrix}|q_{i,s}^{t} − δ_{s}| & M \\ |q_{i,s}^{t}| & M \end{matrix} ≤ \frac{|q_{i,s}^{t}|_{M} + \frac{1}{2}}{|q_{i,s}^{t}|_{M}} ≤ 1 + \frac{1}{2(\frac{M}{2N} + 1)} = 1 + λ (147)

Rewriting

(148)  ∥P_{t}x∥^{2} = ∑_{s=0}^{N−1} | ∑_{\begin{matrix}i=0 \\ s≠i \end{matrix}}^{N−1} \frac{x_{i}}{|q_{i,s}^{t} − δ_{s}|_{M}} \begin{matrix}|q_{i,s}^{t} − δ_{s}| & M \\ |q_{i,s}^{t}| & M \end{matrix} |^{2}

41That is, each row after the first is the cyclic shift by one from the previous row.

42|q_{i,s}^{t} − δ_{s}|_{M} ≥ |q_{i,s}^{t}|_{M} − \frac{1}{2} ≥ \frac{M}{2N} − \frac{3}{2} > 0 since M > 3N

and using the bounds gives

(1 − λ)^{2} ∥Q_{t}x∥^{2} ≤ ∥P_{t}x∥^{2} ≤ (1 + λ)^{2} ∥Q_{t}x∥^{2} (149)

Then since y maximizes ∥Q_{t}x∥^{2},

∥P_{t}x∥^{2} ≤ (1 + λ)^{2} ∥Q_{t}x∥^{2} ≤ (1 + λ)^{2} ∥Q_{t}y∥^{2} ≤ (\frac{1 + λ}{1 − λ})^{2} ∥P_{t}y∥^{2} (150)

giving that we can bound the leftmost term by (\frac{1+λ}{1−λ})^{2} times the norm at y. (\frac{1+λ}{1−λ})^{2}

takes on values between 1 and \frac{225}{169} ≈ 1.33 for M ≥ 16N, better than the constant 4 in [55] and [57].

Combined with corollary A.9 this allows us to bound term 141:

(151)  ∑_{t=−β}^{β} ∑_{s=0}^{N−1} | ∑_{\begin{matrix}i=0 \\ s≠i \end{matrix}}^{N−1} \frac{x_{i}}{|q_{i,s}^{t}|_{M}} |^{2} ≤ ∑_{t} \frac{225}{169} ∑_{s=0}^{N−1} | ∑_{\begin{matrix}i=0 \\ s≠i \end{matrix}}^{N−1} \frac{\frac{1}{\sqrt{N}}}{|q_{i,s}^{t}|_{M}} |^{2}

≤ (2β + 1) \frac{225}{169} \frac{N}{N} (\frac{4N ln N}{M} )^{2} (152)

≤ \frac{M}{N} \frac{225}{169} (\frac{4N ln N}{M} )^{2} (153)

≤ \frac{22N ln^{2} N}{M} (154)

Now we bound the other two terms, 142 and 143. We need the following fact, which can be shown with calculus: the expression |∑_{i=0}^{N−1} a_{i}x_{i}| subject to the con-

dition ∑_{i=0}^{N−1} x_{i}^{2} = 1, has maximum value \sqrt{∑_{i=0}^{N−1} a_{i}^{2}}. Then term 142 can be bounded using a similar technique as in the proof of lemma A.9. Again we take γ = \frac{1}{2} − \frac{N}{M}.

(155)  ∑_{s with α∈C_{s}} | ∑_{\begin{matrix}i=0 \\ s≠i \end{matrix}}^{N−1} \frac{x_{i}}{|q_{i,s}^{α}|_{M}} |^{2} ≤ ∑_{s} |\sqrt{∑_{\begin{matrix}i=0 \\ s≠i \end{matrix}}^{N−1} \frac{1}{|q_{i,s}^{α}|_{M}^{2}}} |^{2}

≤ N \frac{2N^{2}}{M^{2}} (\frac{1}{γ^{2}} + ∑_{a=1}^{\frac{N−1}{2}} \frac{1}{(\frac{1}{2} − \frac{N}{M} + a)^{2}} ) (156)

≤ \frac{2N^{3}}{M^{2}} (\frac{1}{γ^{2}} + \frac{1}{γ} − \frac{1}{\frac{N−1}{2} + γ} ) (157)

≤ \frac{16N^{3}}{M^{2}} (158)

Term 143 is bound with the same method and result, and adding these three bounds gives the desired inequality 139. □

We now use these lemmata to bound the tails ∥∑_{i} û_{i}|T^{i}⟩∥.

Lemma A.11. Given three integers: an odd integer N ≥ 13, L ≥ 2 a power of two, and M ≥ 16N a power of two, then

(159)  ∥ ∑_{i=0}^{N−1} û_{i}|T^{i}⟩∥ ≤ \frac{2}{π} \sqrt{\frac{22 ln^{2} N}{L} + \frac{32N^{2}}{LM}}

Proof.

(160)  ∥ ∑_{i=0}^{N−1} û_{i}|T^{i}⟩∥^{2} = ∑_{k=0}^{M−1} | ∑_{\begin{matrix}i=0 \\ k∉(i) \end{matrix}}^{N−1} û_{i}T_{k}^{i}|^{2}

(161)  ≤ ∑_{k} \frac{4M}{π^{2}LN} ( ∑_{\begin{matrix}i=0 \\ k∉(i) \end{matrix}}^{N−1} \frac{|û_{i}|}{|k − \frac{M}{N} i|_{M}} )^{2}

(162)  ≤ \frac{4M}{π^{2}LN} (\frac{22N ln^{2} N}{M} + \frac{32N^{3}}{M^{2}} )

Taking square roots gives the result. Note that the requirements of lemma A.7 are satisfied when obtaining line 161, since we avoid the k = i = 0 case, and (M, N) = 1. □

Next we show that the shifted |S^{i}⟩ are close to the |B^{i}⟩, which will allow us to show the algorithm output is close to a tensor product.

Lemma A.12.

(163)  ∥|S^{i}⟩ − |B^{i}⟩∥ ≤ \frac{πLN}{M\sqrt{3}}

Proof. Recall |S^{i}⟩ = ∑_{b∈(i)} A_{b−i′ mod M}^{0}|b⟩ and |B^{i}⟩ = ∑_{b∈(i)} A_{b}^{i}|b⟩. It is important these are supported on the same indices! Also recall that |A^{i}⟩ = F_{M}F_{LN}^{−1}|Li⟩ and that F_{M} is unitary. Then (dropping mod M throughout for brevity)

(164)  ∥|S^{i}⟩ − |B^{i}⟩∥^{2} = ∥ ∑_{b∈(i)} A_{b−i′}^{0}|b⟩ − ∑_{b∈(i)} A_{b}^{i}|b⟩∥^{2}

(165)  ≤ ∥ ∑_{k=0}^{M−1} A_{k−i′}^{0}|k⟩ − ∑_{k=0}^{M−1} A_{k}^{i}|k⟩∥^{2}

(166)  = ∥F_{M}^{−1} ( ∑_{k=0}^{M−1} A_{k}^{0}|k + i′⟩ − |A^{i}⟩) ∥^{2}

(167)  = ∑_{a=0}^{LN−1} |\frac{1}{\sqrt{LN}} ω_{M}^{−ai′} − \frac{1}{\sqrt{LN}} ω_{N}^{−ai}|^{2}

(168)  = \frac{1}{LN} ∑_{a=0}^{LN−1} |ω_{M}^{−ai′} (1 − ω_{M}^{aδ_{i}})|^{2}

and this can be bounded by

\frac{1}{LN} ∑_{a=0}^{LN−1} |\frac{2πaδ_{i}}{M} |^{2} ≤ \frac{π^{2}}{LNM^{2}} ∑_{a=0}^{LN−1} a^{2} ≤ \frac{π^{2}}{LNM^{2}} \frac{(LN)^{3}}{3} (169)

Taking square roots gives the bound. □

In the above proof, to obtain line 165 we needed that |S^{i}⟩ and |B^{i}⟩ have the same support, but |S^{i}⟩ is a shifted version of |B^{0}⟩, so we implicitly needed all the sets (i) to have the same cardinality. This is not satisfied in [57] (although it is needed) but is met in [55].

For the rest of the section we need a set which is (0) without mod M applied: let Λ be those integers in the open interval (− ⌊\frac{M}{2N} − \frac{1}{2}⌋ , ⌊\frac{M}{2N} − \frac{1}{2}⌋). Then

Lemma A.13.

(170)  Δ|S^{i}⟩ = |i⟩ ∑_{t∈Λ} A_{t}^{0}|t + α⟩

Proof. By definition, |S^{i}⟩ = ∑_{b∈(0)} A_{b}^{0}|b + ⌊\frac{M}{N} i⌉ mod M⟩. Δ (b + ⌊\frac{M}{N} i⌉) = (i, b) (the proof uses (M, N) = 1), and Δ a bijection implies Δ|b + ⌊\frac{M}{N} i⌉ mod M⟩ = |i⟩|b + α⟩. The rest follows^{43}. □

Main results. Now we are ready to use the above lemmata to prove the main theorem.

Theorem A.14. Given three integers: an odd integer N ≥ 13, L ≥ 16 a power of two, and M ≥ LN a power of two. Then the output |v⟩ of the algorithm in section A.2.3 satisfies

(171)  ∥|v⟩ − F_{N}|u⟩ ⊗ ∑_{t∈Λ} A_{t}^{0}|t + α⟩∥ ≤ \frac{2}{π} \sqrt{\frac{22 ln^{2} N}{L} + \frac{32N^{2}}{LM}} + \frac{πLN}{M\sqrt{3}}

Proof. Note

(172)  |û⟩ := F_{N}|u⟩ = ∑_{i=0}^{N−1} û_{i}|i⟩  F_{M}|u_{L}⟩ = ∑_{i=0}^{N−1} û_{i}|A^{i}⟩

Using lemma A.13 and that Δ is unitary allows us to rewrite the left hand side as

(173) ∥|v⟩ − ∑_{\begin{matrix}s=0 \\ t∈C_{s} \end{matrix}}^{N−1} û_{s}A_{t}^{0}|s⟩|t + α⟩∥ = ∥ΔF_{M}|u_{L}⟩ − ∑_{s=0}^{N−1} û_{s}Δ|S^{s}⟩∥

(174)  = ∥ ∑_{s=0}^{N−1} û_{s}|A^{s}⟩ − ∑_{s=0}^{N−1} û_{s}|S^{s}⟩∥

(175)  = ∥ ∑_{s=0}^{N−1} û_{s}(|B^{s}⟩ + |T^{s}⟩) − ∑_{s=0}^{N−1} û_{s}|S^{s}⟩∥

43It is tempting to use C_{0} instead of Λ, but this is not correct in all cases.

By the triangle inequality this is bounded by

∥ ∑_{s=0}^{N−1} û_{s}|T^{s}⟩)∥ + ∥ ∑_{s=0}^{N−1} û_{s}|B^{s}⟩) − ∑_{s=0}^{N−1} û_{s}|S^{s}⟩∥ (176)

which in turn by lemmata A.11 and A.12 is bounded by

\frac{2}{π} \sqrt{\frac{22 ln^{2} N}{L} + \frac{32N^{2}}{LM}} + \frac{πLN}{M\sqrt{3}}\sqrt{∑_{s} |û_{s}|^{2}} (177)

The last expression has ∥|û⟩∥ = 1, which gives the result. Note that to obtain line 177 we needed the supports of the |B^{s}⟩ disjoint, and that the |S^{i}⟩ and |B^{i}⟩ have the same support^{44}. □

This shows that the output of the algorithm in section A.2.3 is close to a tensor product of the desired output F_{N}|u⟩ and another vector (which is not in general a unit vector). Since a quantum state is a unit vector, we compare the output to a unit vector in the direction of our approximation via:

Lemma A.15. Let a⃗ be a unit vector in a finite dimensional vector space, and b⃗ any vector in that space. For any 0 ≤ ϵ ≤ 1, if ∥a⃗ − b⃗∥ ≤ ϵ then the unit vector b⃗′

in the direction of b⃗ satisfies ∥a⃗ − b⃗′ ∥ ≤ ϵ\sqrt{2}.

Proof. Simple geometry shows the distance is bounded by \sqrt{2(1 − \sqrt{1 − ϵ^{2}})}, and this expression divided by ϵ has maximum value \sqrt{2} on (0, 1]. The ϵ = 0 case is direct. □

So we only need a \sqrt{2} factor to compare the algorithm output with a unit vector which is F_{N}|u⟩ tensor another unit vector. We let |ψ⟩ denote the unit length vector in the direction of ∑_{t∈Λ} A_{t}^{0}|t + α⟩ for the rest of this paper.

For completeness, we repeat arguments from [57, 65] to obtain the operation complexity and probability distribution, and we show concrete choices for M and L achieving a desired error bound.

To show that measuring the first register gives measurement statistics which are very close to the desired distribution, we need some notation. Given two probability distributions D and D′ over {0, 1, …, M − 1}, let |D − D′| = ∑_{k=0}^{M−1} |D(k) − D′(k)| denote the total variation distance. Then a result^{45} of Bernstein and Vazirani [18] states that if the distance between any two states is small, then so are the induced^{46} probability distributions:

Lemma A.16 ([18], Lemma 3.6). Let |α⟩ and |β⟩ be two normalized states, inducing probability distributions D_{α} and D_{β}. Then for any ϵ > 0

(178)  ∥|α⟩ − |β⟩∥ ≤ ϵ ⇒ |D_{α} − D_{β}| ≤ 2ϵ + ϵ^{2}

independent of what basis is used for measurement.

44This is not satisfied in [55], and the overlapping portions make that proof invalid.

45Their statement is a bound of 4ϵ, but their proof gives the stronger result listed above. We choose the stronger form to help minimize the number of qubits needed for simulations.

46The induced distribution from a state |ϕ⟩ is D(k) = |⟨k|ϕ⟩|^{2}.

Combining this with theorem A.14 and lemmata A.15 and A.16 gives the final result

Theorem A.17.

1) Given an odd integer N ≥ 13, and any \sqrt{2} ≥ ϵ > 0. Choose L ≥ 16 and M ≥ LN both integral powers of 2 satisfying

(179)  \frac{2}{π} \sqrt{\frac{22 ln^{2} N}{L} + \frac{32N^{2}}{LM}} + \frac{πLN}{M\sqrt{3}} ≤ \frac{ϵ}{\sqrt{2}}

Then there is a unit vector |ψ⟩ such that the output |v⟩ of the algorithm in section A.2.3 satisfies

(180)  ||v⟩ − F_{N}|u⟩ ⊗ |ψ⟩∥ ≤ ϵ

2) We can always find such an L and M by choosing

(181)  L = c_{1} \frac{\sqrt{N}}{ϵ^{2}}
(182)  M = c_{2} \frac{N^{\frac{3}{2}}}{ϵ^{3}}

for some constants c_{1}, c_{2} satisfying

(183)  65 ≤ c_{1} ≤ 2 × 65
(184)  735 ≤ c_{2} ≤ 2 × 735

3) The algorithm requires ⌈log M⌉ + 2 qubits. By claim 2 a sufficient number of qubits is then ⌈12.53 + 3 log \frac{\sqrt{N}}{ϵ} ⌉. The algorithm has operation complexity O(log M(log log M + log 1/ϵ)). Again using claim 2 yields an operation complexity of

(185)  O (log \frac{\sqrt{N}}{ϵ} (log log \frac{\sqrt{N}}{ϵ} + log 1/ϵ))

4) The induced probability distributions D_{v} from the output and D from F_{N}|u⟩⊗ |ψ⟩ satisfy

(186)  |D_{v} − D| ≤ 2ϵ + ϵ^{2}

Proof. Claim 1 follows directly from theorem A.14 and lemma A.15. Claim 1 and lemma A.16 give claim 4.

To get claim 2, note that for the bound to be met, we must have \frac{ln^{2} N}{L} < ϵ^{2}, \frac{N^{2}}{LM} < ϵ^{2}, and \frac{LN}{M} < ϵ. Trying to keep M small as N and ϵ vary leads to the forms for L and M chosen. If we substitute lines 181 and 182 into 179 and simplify, we get

(187)  \frac{4}{π} \sqrt{\frac{11 ln^{2} N}{c_{1}\sqrt{N}} + \frac{16ϵ^{3}}{c_{1}c_{2}}} + \frac{π\sqrt{2}}{\sqrt{3}} \frac{c_{1}}{c_{2}} ≤ 1

The left hand side is largest when ϵ = \sqrt{2} and N = 55, so it is enough to find constants c_{1} and c_{2} such that

(188)  \frac{4}{π} \sqrt{\frac{11 ln^{2} 55}{c_{1}\sqrt{55}} + \frac{32\sqrt{2}}{c_{1}c_{2}}} + \frac{π\sqrt{2}}{\sqrt{3}} \frac{c_{1}}{c_{2}} ≤ 1

Ultimately we want L and M to be powers of two, so we find a range for each of c_{1} and c_{2} such that the upper bound is at least twice the lower bound, and such that all pairs of values (c_{1}, c_{2}) in these ranges satisfy inequality 188. To check that the claimed ranges work, note that for a fixed c_{1}, the expression increases as c_{2} decreases, so it is enough to check the bound for c_{2} = 735. After replacing c_{2} in the expression with 735, the resulting expression has first and second derivatives with respect to c_{1} over the claimed range, and the second derivative is positive, giving that the maximum value is assumed at an endpoint. So we only need to check inequality 188 at two points: (c_{1}, c_{2}) = (65, 735) and (2 × 65, 735), both of which work. Thus the bound is met for all (c_{1}, c_{2}) in the ranges claimed. With these choices for M and L, note that L ≥ 16 and M ≥ LN ⇔ c_{2} ≥ ϵc_{1}, which is met over the claimed range, so all the hypothesis for claim 1 are satisfied.

Finally, to prove claim 3, algorithm A.2.3 and the proof of lemma A.5 give that we need ⌈log N⌉ qubits in the first register and max{⌈log L⌉ , ⌈log(2α + 1)⌉} qubits in the second register. L ≤ \frac{M}{N} < 2α+1 gives that it is enough to have ⌈log(2α + 1)⌉ qubits in the second register. Then 2α + 1 ≤ \frac{M}{2N} + 2 gives

(189) ⌈log(2α + 1)⌉ ≤ ⌈1 + log M − log N⌉ = 2 + ⌈log M⌉ − ⌈log N⌉

Thus ⌈log M⌉ + 2 is enough qubits^{47} for the algorithm. By claim 2, we can take M ≤ 2 × 735\frac{N^{3/2}}{ϵ^{3}} giving ⌈log M⌉ + 2 ≤ ⌈12.53 + 3 log \frac{\sqrt{N}}{ϵ} ⌉.

As noted in [55] and [57], the most time consuming step in algorithm A.2.3 is the F_{M} Fourier computation. Coppersmith [35] (reproduced in section A.1) shows how to ϵ approximate the quantum Fourier transform for order M = 2^{m} with operation complexity of O(log M(log log M + log 1/ϵ)). Using this to approximate our approximation within error ϵ gives the time complexities in claim 3, finishing the proof. □

Appendix B. Graph Reductions

B.1. Basic Graph Algorithm Relations. Note that G in this section is no longer a group as in the rest of the paper, but a graph.

Following Mathon [94], we show several graph isomorphism problems to be polynomially equivalent. If the ability to solve problem P_{1} allows solving problem P_{2} with polynomially many uses of P_{1}, we say P_{2} is polynomially reducible to P_{1}, and write P_{2} ∝_{p} P_{1}. If P_{2} ∝_{p} P_{1} and P_{1} ∝_{p} P_{2} then we say P_{1} and P_{2} are polynomially equivalent.

Given two undirected graphs G_{1}(V_{1}, E_{1}) and G_{2}(V_{2}, E_{2}) with vertex sets V_{i} and edge sets E_{i}, i = 1, 2, we say G_{1} is isomorphic to G_{2}, written G_{1} ≅ G_{2}, if there exists a bijection ρ : V_{1} → V_{2} such that for all x, y ∈ V_{1}, (x, y) ∈ E_{1} if and only if (ρx, ρy) ∈ E_{2} .

Denote the group of automorphisms of G by aut G. The automorphism partition P denotes the set of disjoint orbits of each vertex under aut G.

47An example requiring ⌈log M⌉ + 2 qubits is M = 1024, N = 65, so the bound is tight.

We consider the following six problems:

ISO(G_{1}, G_{2})  isomorphism recognition for G_{1} and G_{2},
IMAP(G_{1}, G_{2})  isomorphism map from G_{1} onto G_{2} if it exists,
ICOUNT(G_{1}, G_{2}) number of isomorphisms from G_{1} to G_{2},
ACOUNT(G)  number of automorphisms of G,
AGEN(G)  generators of the automorphism group of G,
APART(G)  automorphism partition of G.

Surprisingly,

Theorem B.1. The problems ISO, IMAP, ICOUNT, ACOUNT, AGEN, and APART are polynomially equivalent.

Before proving this we define some notation. Suppose G(V, E) is a graph with n vertices. We define graph labels: Let G_{v_{1},...,v_{k}} denote a copy of G with unique distinct labels attached to the vertices v_{1}, …, v_{k} ∈ V. This can be accomplished in the following manner. To vertex v_{m}, 1 ≤ m ≤ k, attach label “m”, which is a new graph using 2n + m + 3 vertices as follows:

[figure: v_{m}; ^{n + 1}; ^{n + 1}; \overbrace{m}]

This modification has the property that vertices v_{1}, …, v_{k} are fixed by any ρ ∈ aut G_{v_{1},...,v_{k}}, and also there is a natural inclusion aut G_{v_{1},...,v_{k}} ⊆ aut G, obtained by ignoring the labels in aut G. Finally, labelling all vertices adds O(n^{2}) new vertices, retaining polynomial algorithm equivalence between problems on G and G_{v_{1},...,v_{k}}.

Proof. (Following Mathon [94])

IMAP ∝_{p} ISO: Let v_{1}, …, v_{n} be the vertices of G_{1}. If G_{2} does not have n vertices then there is no isomorphism. Otherwise use ISO at most n times to find a u_{1} ∈ V_{2} such that there is an isomorphism G_{1v_{1}} ≅ G_{2u_{1}}, otherwise there is no isomorphism. If such a u_{1} is found, there is an isomorphism ρ mapping v_{1} → u_{1}. Continue fixing v_{1}, …, v_{j}, u_{1}, …, u_{j−1} and searching for u_{j} ∈ V_{2}. This constructs an isomorphism if it exists, calling ISO O(n^{2}) times.

ACOUNT ∝_{p} ISO: For a given labelling G_{v_{1},...,v_{k}} of a graph G let aut G_{v_{1},...,v_{k}} be the corresponding automorphism group, which is the subgroup of aut G that fixes the vertices v_{1}, …, v_{k}. We will show that |aut G_{v_{1},...,v_{k−1}}| = d_{k}|aut G_{v_{1},...,v_{k}}|, where d_{k} is the size of the orbit π_{k} of v_{k} in aut G_{v_{1},...,v_{k−1}}. For 1 ≤ i ≤ d_{k} let ϕ_{i} ∈ aut G_{v_{1},...,v_{k−1}} be an automorphism which maps the i^{th} vertex of π_{k} onto v_{k}. Then every τ ∈ aut G_{v_{1},...,v_{k−1}} is a product of a unique ϕ ∈ {ϕ_{1}, …, ϕ_{d_{k}}} and a unique ψ ∈ aut G_{v_{1},...,v_{k}}. Since |aut G_{v_{1},...,v_{n}}| = 1, |aut G| = d_{1}d_{2} … d_{n}, and each d_{k} can be found by solving ISO at most n − k times. Thus we compute |aut G| by calling ISO at most O(n^{2}) times.

ICOUNT ∝_{p} ISO: Let N_{I} be the number of isomorphisms from G_{1} onto G_{2}. If G_{1} ≇ G_{2} then N_{I} = 0 is determined with one call to ISO. Otherwise we claim N_{I} = |aut G_{1}| = |aut G_{2}|, in which case we use ACOUNT on G_{1} and on G_{2}, calling ISO O(n^{2}) times as above. The claim is proved by the fact that if σ : V_{1} → V_{2} is an isomorphism from G_{1} onto G_{2} and ρ is an automorphism of G_{2} then ρ∘σ is also a graph isomorphism. Moreover any isomorphism σ′ can be uniquely expressed as σ′ = ρ′ ∘ σ where ρ′ ∈ |aut G_{2}|. This 1 − 1 correspondence between |aut G_{2}| and the number of isomorphisms G_{1} → G_{2} proves the claim.

APART ∝_{p} ISO: Two vertices u, v ∈ V of a graph G belong to the same cell of the automorphism partition P of G if G_{u} ≅ G_{v} for identical labels of u and v. Hence at most O(n^{2}) calls to ISO are needed to find P, trying all combinations of u and v.

AGEN ∝_{p} ISO: Applying IMAP to the graphs G_{v_{1},...,v_{k}} and G_{v_{1},...,v_{k−1},v_{l}} with identical labels for k + 1 ≤ l ≤ n we determine the sets of automorphisms Φ_{k} = {ϕ_{1}, …, ϕ_{d_{k}}} at level k (using notation from above). From the proof of IMAP ∝_{p} ISO it follows that the set Φ_{1} ⋃ ⋯ ⋃ Φ_{n} of maps generates aut G. Since d_{k} ≤ n − k + 1 implies

∑_{k=1}^{n} d_{k} ≤ n^{2}

we see that at most O(n^{4}) calls to ISO solve AGEN. This order can be reduced to O(n^{3}) using APART to find the partition of G_{v_{1},...,v_{k}} and by generating only one ϕ_{i} for every feasible orbit in V \ {v_{1}, …, v_{k}} at each level k. It is easily shown at most n generators are produced in this case.

ISO ∝_{p} IMAP, ICOUNT: A single call to either IMAP or ICOUNT gives ISO.

From now on assume G_{1} and G_{2} are each connected (otherwise we may use their complements).

ISO ∝_{p} ACOUNT: Apply ACOUNT to G_{1}, G_{2}, and G_{3} = G_{1} ⋃ G_{2}. If |aut G_{1}| = |aut G_{2}| and |aut G_{1}| · |aut G_{2}| ≠ |aut G_{3}| then G_{1} ≅ G_{2}, else G_{1} ≇ G_{2}.

ISO ∝_{p} AGEN: Apply AGEN to G_{3} = G_{1} ⋃ G_{2}. If σ(v) = u for some v ∈ V_{1}, u ∈ V_{2}, and σ ∈ aut G_{3} then G_{1} ≅ G_{2}, else G_{1} ≇ G_{2}. From the proof of AGEN ∝_{p} ISO we can assume we have at most n^{2} generators of aut G to check, so this can be checked in at most n^{4} = |V_{1}||V_{2}||n^{2}| operations, assuming constant time to check one.

ISO ∝_{p} APART: Apply APART to G_{3} = G_{1} ⋃ G_{2}. If v, u belong to the same cell of the partition P of G_{3} for some u ∈ V_{1}, u ∈ V_{2}, then G_{1} ≅ G_{2}, otherwise G_{1} ≇ G_{2}. This can be checked quickly by scanning the partition once.

This completes the proof of the theorem. □

Finally, following [81, Theorem 1.31], we can reduce this to efficient algorithms solving the following graph automorphism questions:

• GA(G) - Given a graph G, decide whether its automorphism group has a nontrivial automorphism.

• GA1(G) - Given that |aut G| ∈ {1, 2}, determine |aut G| We note that GA(G) seems easier than ISO(G_{1}, G_{2}) [81]. As above, we are able to reduce the seemingly more complex GA to GA1:

Theorem B.2. GA ∝_{p} GA1

For a proof, see [81].

So there are many ways to approach the graph isomorphism and graph automorphism problems, some of which at first glance seem easier than the original question. For the purposes of quantum computation, and in particular reducing these questions to finding hidden subgroups of S_{n}, see the next section (B.2).

As a final note, there are far reaching proofs that show determining isomorphism between any finite algebraic structures (such as rings, groups, fields, etc.) is polynomial-time many-to-one reducible to ISO, making a fast ISO algorithm extremely useful across many disciplines [95]. These are a few of the reasons that an efficient ISO algorithm has seen such strong research interest.

B.2. Quantum HSP for Graph Isomorphism. We want to show how being able to find hidden subgroups H of S_{n} allows solving ISO, which then gives efficient algorithms for all the problems in the previous section. We define our hidden function f : S_{n} → {permutations of G} by f(π) = π(G). So f applies a permutation π to the vertices of G. We need to show f separates cosets of H = aut G, and that f is efficiently computable. Then an algorithm giving generators of H, i.e., giving an algorithm for AGEN, gives the desired algorithm for ISO.

To make this precise, suppose G is represented on a computer by a list of pairs (v_{i}, v_{j}) of vertices where there is an edge from vertex i to vertex j. Assume this list is sorted and each pair is sorted. We define f at the programming level as taking a permutation (which can just be a list π of n pairs i → π(i)) and doing the following two steps: apply the permutation to the integers v_{i} in time O(# edges), then sort the result efficiently by usual methods (Quicksort, etc.). Thus f can be computed efficiently, and leaves G in a state where comparisons can be done quickly (that is, G ≅ π(G) if and only if G = f(π) using this encoding, which you should check).

Let S_{n} act on the n vertices of G, and let H = aut(G) < S_{n}. To show f separates cosets of H, we want f(π_{1}) = f(π_{2}) if and only if π_{1}H = π_{2}H, which follows from

f(π_{1}) = f(π_{2}) ⇔ π_{1}(G) = π_{2}(G) ⇔ π_{2}^{−1}π_{1}G = G ⇔
π_{2}^{−1}π_{1} ∈ aut G ⇔ π_{2}^{−1}π_{1}H = H ⇔ π_{1}H = π_{2}H.

This shows f can be used in the standard quantum Fourier sampling algorithm to find generators for H. If this can be done efficiently is an open question.

Appendix C. Quantum Mechanics Details

C.1. The Rules and Math of Quantum Mechanics.

C.1.1. Enter the Qubit. First we start out with the basic block of quantum computing. Analogous to the bit in classical computing, there is a quantum bit in quantum computing. A classical bit is a 2 state system, with the states denoted 0 and 1. A classical bit is always in one of those states or the other, and measuring the state return a 0 or 1 with certainty. n bits can be in exactly one of 2^{n} different ordered states, usually denoted 000 … 00, 000 … 01,…,111 … 11.^{48}

Quantum bits (which we shall call qubits) similarly can exist in two states, which we call |0⟩ and |1⟩. However, they behave as if existing in many “in between” states. A quantum bit can be physically represented by any two state (or more) system, such as electron spin up and down, photon energy states, atomic energy levels, molecular vibrational freedom, and many others. For our purposes we assume physical representations are available (they are).

To make the concept of a qubit precise, we define Definition C.1 (Qubit). A qubit (or quantum-bit) is a unit vector in ℂ^{2}.

48“There are only 10 kinds of people in the world. Those who understand binary and those who don’t.”

Definition C.2 (State vector). The state of a quantum system is a (column) vector in some vector space, written |ψ⟩.

With this definition, we fix an orthonormal basis of (column) vectors, labelled |0⟩ = \binom{1}{0} and |1⟩ = \binom{0}{1}. It will turn out that physically, we can only distinguish orthogonal quantum states, thus the orthogonal requirement. And considerations of probability will make the normality convenient, thus we fix an orthonormal basis. Any such basis of ℂ^{2} will work, but we choose the above representations since they are good to work with. Finally, we make a qubit a unit vector because, again, it makes calculations cleaner, and has some physical significance.

Now for the differences from classical bits. A qubit can be any unit vector, not just those corresponding to |0⟩ and |1⟩. A qubit can be in the state

(190)  α|0⟩ + β|1⟩

where α and β are complex numbers, with |α|^{2} + |β|^{2} = 1. While it only takes one “bit” to fully describe the state of a classical bit, it takes two complex numbers to completely describe the state of one qubit, which intuitively is infinitely more information! However we will see there are practical limitations to the amount of “information” one can retrieve from a single qubit.

This gives us the first of four postulates of quantum mechanics:

Quantum Mechanics Postulate 1: State Space Associated to an isolated physical system is a complex vector space with inner product (a Hilbert space) known as the state space of the system. The system is completely described by its state vector, which is a unit vector in the system’s state space. Thus an n-qubit system is a unit vector in ℂ^{2^{n}}.

We will explain the inner product below (we can use the Euclidean one).

C.1.2. How to “Measure” a Qubit. In principle you could store the knowledge in the Library of Congress on one qubit, but you could never retrieve it. When you read out the value in a qubit in the state in equation 190, it returns the state |0⟩ with probability |α|^{2}, or it returns the state |1⟩ with probability |β|^{2}, and then the qubit assumes the state just returned. Thus we can only get one state back out from the qubit, which collapses (destroys) the rest of the information in the qubit.

For example, suppose we have a qubit in the state

(191)  |ψ⟩ = \frac{1}{\sqrt{2}}|0⟩ + \frac{1}{\sqrt{2}}|1⟩

What are the odds that it returns a |1⟩ when measured? A |0⟩?

This generalizes to multiple qubits as we soon see.

One last point is worth mentioning - there is a useful way to visualize operations on a single qubit, using the Bloch sphere. It will turn out that under observation, states |ψ⟩ and e^{iθ}|ψ⟩ have the same behavior, so we can modify a state up to the phase iθ, where i = \sqrt{−1}. So given a single qubit state α|0⟩ + β|1⟩, we can remove a phase to write

(192)  α|0⟩ + β|1⟩ = e^{iγ} (cos \frac{θ}{2}|0⟩ + e^{iφ} sin \frac{θ}{2}|1⟩)

Since the phase out front has no effect on measurements, we can use θ and φ for spherical coordinates

(193)  x = cos φ sin θ
(194)  y = sin φ sin θ
(195)  z =  cos θ

This allows us to picture a qubit as a point on a three dimensional sphere, and visualize operations upon a qubit.

Unfortunately, this has no known generalization to multiple qubits

C.1.3. Qubits Galore. Similar to concatenating n classical bits to get “bitstrings”, we concatenate qubits to get larger systems. Two qubits form a space spanned by four vectors

(196)  |0⟩ ⊗ |0⟩, |0⟩ ⊗ |1⟩, |1⟩ ⊗ |0⟩, and |1⟩ ⊗ |1⟩

where we will define the “tensor product” ⊗ in a moment. Shorthand for the above expressions is

(197)  |00⟩, |01⟩, |10⟩, and |11⟩

Definition C.3. The tensor product of two vectors x = (x_{1}, x_{2}, …, x_{n})^{T} and y = (y_{1}, y_{2}, …, y_{m})^{T} as the vector in nm dimensional space given by

(198)  x ⊗ y = (\begin{matrix}x_{1}y \\ x_{2}y \\ … \\ x_{n}y \end{matrix}) = (\begin{matrix}x_{1}y_{1} \\ x_{1}y_{2} \\ … \\ x_{1}y_{m} \\ x_{2}y_{1} \\ … \\ x_{n}y_{m} \end{matrix})

Homework C.1. Check this definition does not depend on a choice of basis.

Now we can check the second basis element (dictionary ordering)

(199)  |01⟩ = |0⟩ ⊗ |1⟩

= \binom{1}{0} ⊗ \binom{0}{1} (200)

(201)  = (\begin{matrix}1\binom{0}{1} \\ 0\binom{0}{1} \end{matrix}) = (\begin{matrix}0 \\ 1 \\ 0 \\ 0 \end{matrix})

and we get the second usual basis element of ℂ^{4}. This works in general; that is, the vector corresponding to the state |n⟩ where n is a binary number, is the (n + 1)^{th} standard basis element. We also use the decimal shorthand sometimes: |32⟩ is the 33rd standard basis vector in some space which would be clear from context.

Back to the inner product from postulate 1: We write it using the “braket” notation, where the symbol |k⟩ is called a ket, and the dual ⟨j| is a bra. Given a state (ket) |ψ⟩ = ∑ α_{j}|j⟩, we define the dual (bra) as the conjugate transpose, that is,

(202)  ⟨ψ| = |ψ⟩^{†} = ∑ α_{j}^{∗}⟨j|

Together we write ⟨j|k⟩, which is the “braket” of states |j⟩ and |k⟩. Since the states are orthonormal, ⟨j|k⟩ is 1 if and only if j = k, otherwise it is zero. We extend this inner product ⟨−, −⟩ to general states via linearity. Thus states |ψ_{1}⟩ = ∑ α_{j}|j⟩ and |ψ_{2}⟩ = ∑ β_{k}|k⟩ give

⟨ψ_{1}|ψ_{2}⟩ = ∑_{j} α_{j}^{∗}⟨j| ∑_{k} β_{k}|k⟩
= ∑_{j,k} α_{j}^{∗}β_{k}⟨j|k⟩ = ∑_{m} α_{m}^{∗}β_{m}

So we have the equivalent notations for a 5-qubit state:

|1⟩ ⊗ |0⟩ ⊗ |0⟩ ⊗ |1⟩ ⊗ |0⟩ = |10010⟩
= |18⟩

It is worth noting that not all composite states are simple tensor products of single states. One of the simplest is one of the 2 qubit Bell states, β_{00} = \frac{|00⟩+|11⟩}{\sqrt{2}}. This is an example of an entangled state which turns out to be a very useful computational resource later.

Homework C.2. Prove β_{00} is not of the form |ψ⟩ ⊗ |φ⟩.

When appropriate, we may drop the normalization factor to clean up calculations. Then we could write β_{00} = |00⟩ + |11⟩, with the understanding this needs to be normalized.

C.1.4. Measuring Revisited. Now - how about measuring these states? An arbitrary 2-qubit state is

|ψ⟩ = α_{00}|00⟩ + α_{01}|01⟩ + α_{10}|10⟩ + α_{11}|11⟩

with complex valued α_{ij}. Requiring ∑_{ij} |α_{ij}|^{2} = 1 is called the “normalization requirement”, and we assume all states are normalized. Sometimes to avoid clutter we will drop the coefficients.

Suppose we only measure the first qubit of |ψ⟩. We will obtain |0⟩ with probability |α_{00}|^{2} + |α_{01}|^{2}, that is, we obtain a state with probability equal to the sum of the magnitudes of all states that contribute. After measuring, we know the first qubit is |0⟩, so only those type of states are left, causing the new state to be

|ψ^{∗}⟩ = \frac{α_{00}|00⟩ + α_{01}|01⟩}{\sqrt{|α_{00}|^{2} + |α_{01}|^{2}}}

Notice the new normalization factor in the denominator. Again, this idea generalizes to arbitrary (finite) dimension.

Thus we have a way to denote arbitrary quantum states on n qubits:

(203)  |ψ⟩ = ∑_{j=0}^{2^{n}−1} α_{j}|j⟩

where the α_{i} are complex numbers satisfying the normalization requirement. Measuring |ψ⟩ returns state |j⟩ with probability |α_{j}|^{2}, and then becomes state |j⟩ C.1.5. Qubit Evolution. We would like our quantum computers to work similar to classical computers. Classically, a very basic operation at the bit level is the NOT gate, which flips bits, that is 0 becomes 1 and 1 becomes 0. So the quantum version would take the state α|0⟩ + β|1⟩ ⟶^{NOT} β|0⟩ + α|1⟩. It is east to check the matrix

(204)  X = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )

performs the desired operation, by multiplying X on the left of the state. The name X is historical, and we will see the exponential of X rotates qubits around the x-axis on the Bloch sphere. Since X acts like a NOT gate on a qubit, it is often called the NOT operator.

For fun, we compute “the square root of NOT.” We want an operator \sqrt{NOT} that when applied twice to a qubit, has the effect of NOT. This procedure will be useful when we need to construct quantum circuits and when we explain exponentials.

In general, given a function f(t) of one complex variable, we extend this definition to diagonalizable matrices M = diag(m_{1}, m_{2}, … m_{n}) via:

(205)  f(M) = diag(f(m_{1}), f(m_{2}), …, f(m_{n}))

Since we want \sqrt{X}, we need to diagonalize X. Note the eigenvectors of X are \binom{1}{1} and \binom{1}{−1}. Setting a matrix P with these as column vectors, we have under this basis change the diagonal matrix

P XP^{−1} = ( \begin{matrix}1 & 1 \\ 1 & −1 \end{matrix} ) ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) ( \frac{1}{2} −\frac{1}{2}^{\frac{1}{2}  \frac{1}{2}} )
=  ( \begin{matrix}1 & 0 \\ 0 & −1 \end{matrix} )

Applying f(t) = \sqrt{t}, and changing the basis back gives

P^{−1}f ( \begin{matrix}1 & 0 \\ 0 & −1 \end{matrix} ) P = ( \frac{1}{2} −\frac{1}{2}^{\frac{1}{2}  \frac{1}{2}} ) ( \begin{matrix}1 & 0 \\ 0 & i \end{matrix} ) ( \begin{matrix}1 & 1 \\ 1 & −1 \end{matrix} )
=  \frac{1}{2} ( \begin{matrix}1 + i & 1 − i \\ 1 − i & 1 + i \end{matrix} )
=  \sqrt{NOT}

It is an easy check to see that \sqrt{NOT}^{2} = X.

This process of diagonalizing an operator, applying a function, and restoring the basis will be invaluable later.

Homework C.3. What is the effect of e^{−iθX/2} on the Bloch sphere, where θ is a real number?

C.1.6. A Universal Quantum Gate? It is a basic result in computer science that any circuit can be built with NAND gates, which performs the following operation on two bits a and b:

\begin{matrix}a \ b & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \end{matrix}

Any function on n bits can be built up from NAND gates. However the general function requires exponentially many gates, so in practice we are restricted in the functions we utilize.

So is there a similar “gate” for quantum computing? Yes, and no. It will take a while to answer this precisely, but there are finite (and small) sets of gates sufficient to approximate any desired quantum operation to any degree of accuracy in an efficient manner.^{49}

To understand what operations we can physically apply to a qubit (or set of qubits), we are led to study rules from quantum mechanics. It has become clear that abstract models of computation and information theory should be derived from physical law, rather than as standalone mathematical structures, since it is ultimately physical law that determines computability and information. Observation has led researchers to believe that at the quantum level, the following two facts hold:

• All quantum evolution is reversible. That is very unlike the classical case, where for example NAND is not reversible.^{50} This is illustrated by the fact that an electron in orbit does not emit radiation and spiral into the nucleus.

• Quantum evolution is linear. That is, if an experiment is done on the state |0⟩ and on the state |1⟩, then when performed on mixed states the resulting state is the same state as if the initial two answers were added.

So we are left with “reversible” linear operators on the states, that is, matrices! Since the resulting state should satisfy the normalization requirement also, it turns out that any unitary operation is allowed. Recall U unitary means UU^{†} = I. We now have :

Quantum Mechanics Postulate 2: State Evolution The evolution of a closed quantum system is described by a unitary transformation. That is, the state of a system |ψ⟩ at time t_{1} is related to the state |ψ′⟩ at time t_{2} by a unitary operator U which depends only on the times t_{1} and t_{2},

(206)  |ψ⟩ = U|ψ′⟩

Now we know how to specify quantum states and what is legal for manipulating the state.

C.1.7. Intermission - Linear Algebra Review. We will need several facts, terms, and theorems from linear algebra. It will be easiest to just fire them off: (we also combine some previous facts here for the heck of it) Definition C.4. Let H, A, B, U be linear operators on a vector space V.

(1) H^{†} is the conjugate transpose of H.

(2) H is Hermitian or self-adjoint if H = H^{†}.

(3) |ψ⟩ is a column vector.

(4) ⟨ψ| is the dual to |ψ⟩, defined ⟨v| ≡ |v⟩^{†}.

(5) |ψϕ⟩ = |ψ⟩|ϕ⟩ = |ψ⟩ ⊗ |ϕ⟩.

(6) [A, B] = AB − BA.

(7) {A, B} = AB + BA.

(8) A is normal if A^{†}A = AA^{†}.

(9) U is unitary if U^{†}U = I.

49The Solovay-Kitaev theorem says that for any gate U on a single qubit, and given any ϵ > 0, it is possible to approximate U to a precision ϵ using Θ(log^{c}(1/ϵ)) gates from a fixed, finite set, where 1 ≤ c ≤ 2. Determining c is an open problem.

50Charles Bennett of IBM research showed in the 1970’s that energy is used in computations to destroy information. Lossless computation can theoretically be done with no energy usage whatsoever!

(10) A is positive if ⟨ψ|A|ψ⟩ ≥ 0 for all ψ.

(11) ⟨ψ|A|ϕ⟩ is the inner product of ψ and A|ϕ⟩.

(12) We define specific matrices (the first 4 are the Pauli matrices)

σ_{0} = I,

σ_{1} = σ_{x} = X = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ),

σ_{2} = σ_{y} = Y = ( \begin{matrix}0 & −i \\ i & 0 \end{matrix} ),

σ_{3} = σ_{z} = Z = ( \begin{matrix}1 & 0 \\ 0 & −1 \end{matrix} ),

H = \frac{1}{\sqrt{2}} ( \begin{matrix}1 & 1 \\ 1 & −1 \end{matrix} ), S = ( \begin{matrix}1 & 0 \\ 0 & i \end{matrix} ), T = ( \begin{matrix}1 & 0 \\ 0 & e^{\frac{iπ}{4}} \end{matrix} )

(13) For a unit vector n⃗ = (n_{x}, n_{y}, n_{z}) ∈ ℝ^{3}, define n⃗.σ⃗ ≡ n_{x}σ_{x} + n_{y}σ_{y} + n_{z}σ_{z}.

(14) Bloch Sphere Given a state a|0⟩ + b|1⟩ we may assume a is real by phase rotation. Then define for ϕ ∈ [0, 2π] and θ ∈ [0, π]

(207)  cos (\frac{θ}{2}) = a
(208)  e^{iϕ} sin (\frac{θ}{2}) = b

Then the point on the Bloch Sphere is (cos ϕ sin θ, sin ϕ sin θ, cos θ).

(15) Define the three rotation matrices: R_{x}(θ) = e^{−θXi/2} = cos \frac{θ}{2}I − i sin \frac{θ}{2}X =

( \begin{matrix}cos(θ/2) & −i sin(θ/2) \\ −i sin(θ/2) & cos(θ/2) \end{matrix} )

R_{y}(θ) = e^{−θY i/2} = cos \frac{θ}{2}I − i sin \frac{θ}{2}Y = ( \begin{matrix}cos(θ/2) & − sin(θ/2) \\ sin(θ/2) & cos(θ/2) \end{matrix} )

R_{z}(θ) = e^{−θZi/2} = cos \frac{θ}{2}I − i sin \frac{θ}{2}Z = ( \begin{matrix}e^{−iθ/2} & 0 \\ 0 & e^{iθ/2} \end{matrix} )

(16) For a composite quantum system AB, the partial trace is an operator from density operators on AB to density operators on A defined for tr_{B}(|a_{1}⟩⟨a_{2}|⊗ |b_{1}⟩⟨b_{2}|) = ⟨b_{2}|b_{1}⟩|a_{1}⟩⟨a_{2}|, and extended by linearity. On matrices: let dim A = n, dim B = m, then it takes a mn by mn matrix, and replaces each m by m sub-block with its trace to give a n by n matrix.

(17) The Bell States are the 2-qubit basis states

(209)  |β_{00}⟩ = \frac{|00⟩ + |11⟩}{\sqrt{2}}
(210)  |β_{01}⟩ = \frac{|01⟩ + |10⟩}{\sqrt{2}}
(211)  |β_{10}⟩ = \frac{|00⟩ − |11⟩}{\sqrt{2}}
(212)  |β_{11}⟩ = \frac{|01⟩ − |10⟩}{\sqrt{2}}

Note: The four Pauli matrices (I, X, Y, and Z) have significance, since they form a basis of all linear operators on one qubit, and correspond to similarly named actions on the Bloch sphere.

We can write operators like X in an equivalent operator notation, which is often convenient to use in calculations. Noting that ⟨0| is a row vector, then |0⟩⟨0| is a 2 × 2 matrix. We can write X as:

(213)  X =  |0⟩⟨1| + |1⟩⟨0|
(214)  =  \binom{1}{0}(0 1) + \binom{0}{1}(1 0)
(215)  = ( \begin{matrix}0 & 1 \\ 0 & 0 \end{matrix} ) + ( \begin{matrix}0 & 0 \\ 1 & 0 \end{matrix} ) = ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} )

This is interpreted quickly: X sends state 0 to 1, and vice versa.

Example: As an example calculation, we compute ⟨β_{00}|I_{2}⊗X|β_{10}⟩ two different ways. The first way is matrix multiplication: Noting that |00⟩ = (1, 0, 0, 0)^{T} and |11⟩ = (0, 0, 0, 1)^{T}, we have

⟨β_{00}|I ⊗ X|β_{10}⟩ = (\frac{|00⟩+|11⟩}{\sqrt{2}})^{†} ( \begin{matrix}1 & 0 \\ 0 & 1 \end{matrix} ) ⊗ ( \begin{matrix}0 & 1 \\ 1 & 0 \end{matrix} ) (\frac{|00⟩−|11⟩}{\sqrt{2}}) (216)

(217)  = (\frac{1}{\sqrt{2}})^{2} ( 1 0 0 1 ) ( \begin{matrix}0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix} ) ( \begin{matrix}1 \\ 0 \\ 0 \\ −1 \end{matrix} )

(218)  =  0

For the other method, note as operators we can write I = |0⟩⟨0| + |1⟩⟨1|, and X swaps basis vectors, giving X = |0⟩⟨1| + |1⟩⟨0|. Then we have

(219)  I ⊗ X =  (|0⟩⟨0| + |1⟩⟨1|) ⊗ (|0⟩⟨1| + |1⟩⟨0|)
(220)  = |00⟩⟨01| + |01⟩⟨00| + |10⟩⟨11| + |11⟩⟨10|

where we used the fact |a⟩⟨b|⊗|c⟩⟨d| = |ac⟩⟨bd|. Apply this and use orthonormality,

⟨β_{00}|I ⊗ X|β_{10}⟩ = (\frac{⟨00|+⟨11|}{\sqrt{2}}) (|00⟩⟨01| + |01⟩⟨00| + |10⟩⟨11| + |11⟩⟨10|) (\frac{|00⟩−|11⟩}{\sqrt{2}}) (221)
(222)  =  (\frac{1}{\sqrt{2}})^{2} (0 + 0 + 0 + ⋯ + 0)
(223)  =  0

where we get terms like ⟨00|00⟩⟨01|00⟩ = 1 · 0 = 0.

Homework C.4. Write the matrices above in operator form for practice.

Homework C.5. Compute the eigen-values and eigen-vectors for the matrices defined above. They will be useful.

Homework C.6. Understand the behavior of each matrix above on the Bloch sphere representation of a qubit.

C.1.8. Useful Linear Algebra Theorems.

Theorem C.5 (Cauchy Schwartz Inequality). |⟨v|w⟩|^{2} ≤ ⟨v|v⟩⟨w|w⟩

Theorem C.6 (Spectral Decomposition). Any normal operator M on a vector space V is diagonal with respect to some orthonormal basis for V. Conversely, any diagonalizable operator is normal.

Proof. Sketch: Induct on d = dim V. d = 1 is trivial. Let λ be an eigenvalue of M, P the projector onto the λ eigenspace, and Q the projector onto the orthogonal complement. M = P MP + QMQ is diagonal with respect to some basis (strip off an eigenvalue one at a time...) □

Check: There is a matrix P, with unit eigenvectors as columns, so that P MP^{†} is diagonal, with entries the eigenvalues.

Theorem C.7 (Simultaneous diagonalization). Suppose A and B are Hermitian operators on a vector space V. Then [A, B] = 0 ⇔ there exists an orthonormal basis such that both A and B are diagonal with respect to that basis.

Theorem C.8 (Polar decomposition). Let A be a linear operator on a vector space V. Then there exists a unitary U and positive operators J and K such that

A = UJ = KU

where the unique J and K are given by J ≡ \sqrt{A^{†}A} and K ≡ \sqrt{AA^{†}}. Moreover, A invertible implies U is unique.

Proof. J ≡ \sqrt{A^{†}A} is positive, so spectral gives J = ∑_{i} λ_{i}|i⟩⟨i|, (λ_{i} ≥ 0). Let |ϕ_{i}⟩ = A|i⟩. For λ_{i} ≠ 0, let |e_{i}⟩ = |ϕ_{i}⟩/λ_{i}. Extend to orthogonal basis |e_{i}⟩, and define unitary U ≡ ∑_{i} |e_{i}⟩⟨i|. This satisfies A = UJ. Multiply on left by adjoint A^{†} = JU^{†} giving J^{2} = A^{†}A, so J = \sqrt{A^{†}A}.

Then A = UJ = UJU^{†}U = KU with K = UJU^{†}. This K = \sqrt{AA^{†}}. □

Theorem C.9 (Singular value decomposition). Let A be a square matrix. Then there exists unitary U and V, and diagonal D, such that

A = UDV

The diagonal elements of D are called singular values of A.

Proof. By polar decomposition, A = SJ for S unitary and J positive. By spectral J = T DT^{†}, T unitary, D diagonal with nonnegative entries. U ≡ ST and V ≡ T^{†} completes the proof. □

Theorem C.10. Every unitary 2 × 2 matrix can be expressed as

(224)  (\begin{matrix}e^{iα} & 0 \\ 0 & e^{iα} \end{matrix}) · (\begin{matrix}e^{\frac{iβ}{2}} & 0 \\ 0 & e^{− \frac{iβ}{2}} \end{matrix} ) · (\begin{matrix}cos \frac{γ}{2} & − sin \frac{γ}{2} \\ sin \frac{γ}{2} & cos \frac{γ}{2} \end{matrix} ) · (\begin{matrix}e^{\frac{iδ}{2}} & 0 \\ 0 & e^{− \frac{iδ}{2}} \end{matrix} )

Note: Notice the third matrix is a usual rotation in the plane. The 2nd and 4th matrices are Z-axis rotation on the Bloch sphere, and the first matrix is merely a phase shift of the entire state. This decomposition gives some intuition of how a single qubit operator acts.

Theorem C.11 (Z-Y decomposition for a single qubit). U is a unitary operation on a single qubit. Then there are real numbers α, β, δ, γ such that

U = e^{iα}R_{z}(β)R_{y}(γ)R_{z}(δ)

Note: Similarly there are X-Y, Z-X, etc. decomposition theorems.

Theorem C.12 (ABC corollary). Suppose U is a unitary gate on a single qubit. Then there are unitary operators A, B, and C, such that ABC = I, and U = e^{iα}AXBXC, where α is some overall phase factor.

Proof. Apply theorem C.11 with A ≡ R_{z}(β)R_{y}(γ/2), B ≡ R_{y}(−γ/2)R_{z}(−(δ + β)/2), and C ≡ R_{z}((δ − β)/2). □

This weird looking theorem becomes very useful when trying to construct quantum circuits. It allows one to use a Controlled NOT gate (a circuit that flips a qubit based on the state of another qubit) to contract arbitrary controlled U gates.

C.1.9. Useful Linear Algebra Facts! Here are some facts that help in computations and proofs when dealing with quantum computing.

(1) Any complex n × n matrix A can be written as a sum of 4 positive Hermitian matrices: A = B + iC with B, C Hermitian B = \frac{1}{2} (A^{∗} + A), and C accordingly. Then any Hermitian B can be written as the sum of 2 positive Hermitian matrices B = (B + λI) − λI where −λ is the most negative eigenvalue of B.

(2) Every positive A is of the form BB^{∗}.

(3) |a_{1}⟩⟨a_{2}| ⊗ |b_{1}⟩⟨b_{2}| = |a_{1}b_{1}⟩⟨a_{2}b_{2}| (useful in partial trace operations).

(4) Trace of kets: |ψ⟩ = ∑_{i,j} a_{ij}|ij⟩, when converted to a density matrix ρ = |ψ⟩⟨ψ|, and then the trace is taken over the j, gives

tr_{B}(p) = ∑_{i} (∑_{j} |a_{i,j}|^{2}) |i⟩⟨i|,

so it seems tr_{B}(|ψ⟩) should be something like ∑_{i} \sqrt{∑_{j} |a_{i,j}|^{2}} |i⟩. In particular, tracing out some columns in |011010⟩ removes those columns, but the new kets are not a simple sum of the previous ones... It may be ok to sum probabilities, then sqrt when collapsing, but I am not clear.

(5) Unitary also satisfies UU^{†} = I, so U is normal and has spectral decomposition (all QC ops unitary!).

(6) Unitary preserves inner products.

(7) Positive ⇒ Hermitian ⇒ normal.

(8) A^{†}A is positive for any linear operator A.

(9) Tensor of unitary (resp Hermitian, positive, projector) is unitary (resp,...).

(10) If P = ( \begin{matrix}a & b \\ c & d \end{matrix} ) is invertible, then P^{−1} = \frac{1}{ad−bc} ( \begin{matrix}d & −b \\ −c & a \end{matrix} ).

(11) Given eigenvectors v_{1} and v_{2} of B, with eigenvalues λ_{1} and λ_{2}, create the change of basis matrix P = ( v_{1} v_{2} ). Then the diagonal matrix D is

D = ( \begin{matrix}λ_{1} & 0 \\ 0 & λ_{2} \end{matrix} ) = P^{−1}BP

(12) W is a subspace of V with basis |i⟩. Projection to W is P = ∑_{i} |i⟩⟨i|. Q = I − P is the orthogonal complement.

(13) Eigenvectors with distinct eigenvalues of a Hermitian operator are orthogonal.

(14) n⃗.σ⃗ has eigenvalues ±1 with corresponding eigenvectors ( \begin{matrix}n_{z} ± 1 \\ n_{x} + in_{y} \end{matrix} ).

(15) U unitary ⇒ U has a spectral decomposition ⇒ U is diagonal in some orthonormal basis ⇒ U = diag(e^{iα_{1}}, e^{iα_{2}}, …, e^{iα_{n}}) ⇒ U has a unitary n^{th} root V, V^{n} = U.

(16) tr (|ψ⟩⟨ϕ|) = ⟨ϕ|ψ⟩.

(17) For unit vectors r⃗ and s⃗, (r⃗.σ⃗) · (s⃗.σ⃗) = r⃗ · s⃗I + (r⃗ × s⃗).σ⃗.

C.1.10. Some Basic Identities. There are lots of identities between the operators we have above which will be useful in reducing circuits later on. This is a good place to list some.

[X, Y] = 2iZ [Y, Z] = 2iX [Z, X] = 2iY

{σ_{i}, σ_{j}} = 2δij if i, j ≠ 0 σ_{i}^{2} = I

R_{z}(\frac{π}{2} )R_{x}(\frac{π}{2} )R_{z}(\frac{π}{2} ) = e^{−iπ/2}H

XY X = −Y ⇒ XR_{y}(θ)X = R_{y}(−θ)

HXH = Z HY H = −Y HZH = X

HT H = phase ∗ R_{x}(\frac{π}{4} )

C is CNOT, X_{j} is X acting on qubit j, etc.

\begin{aligned}CX_{1}X & = & X_{1}X_{2} & CY_{1}C & = & Y_{1}X_{2} \\ CZ_{1}C & = & Z_{1} & CX_{2}C & = & X_{2} \\ CY_{2}C & = & Z_{1}Y_{2} & CZ_{2}C & = & Z_{1}Z_{2} \\ R_{z,1}(θ)C & = & CR_{z,1}(θ) & R_{x,2}(θ)C & = & CR_{x,2}(θ) \end{aligned}

For i, j = 1, 2, 3, σ_{j}σ_{k} = δ_{jk}I + i ∑_{l=1}^{3} ϵ_{jkl}σ_{l} where ϵ_{jkl} is the antisymmetric tensor on 3 indices.^{51}

Homework C.7. Check these identities using the matrix form and the operator form to gain mastery of these calculations.

C.1.11. Measuring the Qubits. The final operation we need to understand about qubits is, how can we get information back out of them? The process is called measurement, and there are several equivalent ways to think about it. We will cover the easiest to understand, intuitively and mathematically. However, to gain the precise control over measurements, we will have to resort later to an equivalent, yet more complicated, measurement framework.

Quantum Mechanics Postulate 3: State Measurement Quantum measurements are described by a collection {M_{m}} of measurement operators. These are operators acting on the state space of a system being measured. The index m refers to the measurement outcomes that may occur in the experiment. If the state of the system is |ψ⟩ immediately before the measurement, then the probability that result m occurs is given by

(225)  p(m) = ⟨ψ|M_{m}^{†}M_{m}|ψ⟩

and the state of the system after the measurement is

(226)  \frac{M_{m}|ψ⟩}{\sqrt{p(m)}}

The measurement operators satisfy the completeness equation

(227)  ∑_{m} M_{m}^{†}M_{m} = I

51Exercise 2.43 in Neilsen and Chuang. All of these identities appear in the book, as exercises or in the text.

Finally, note cascaded measurements are single measurements. Thus if your algorithm calls for a succession of measurements, this is equivalent to a single measurement.

C.1.12. Combining States and Partial States. Quantum Mechanics Postulate 4: State Combining The state space of a composite physical system is the tensor product of the state spaces of the component systems. Moreover, if we have systems numbered 1 through n, and system number j is prepared in the state |ψ_{j}⟩, then the joint state of the total system is |ψ_{1}⟩ ⊗ |ψ_{2}⟩ ⊗ … |ψ_{n}⟩.

And that is all there is to quantum mechanics (as far as we are concerned). These four postulates form the basis of all that is known about quantum mechanics, a physical theory that has stood for over seven decades, and is used to explain phenomena at many scales.

However, quantum mechanics does not mesh well with the other main intellectual achievement in theoretical physics in the 20th century, relativity. Combining these two theories into a unified framework has occupied the best minds for over 50 years, and currently superstring theory is the best candidate for this unification.

Using the above postulates gives us an important theorem from Wootters and Zurek [127]:

C.1.13. The No Cloning Theorem.

Theorem C.13. The No Cloning Theorem.It is impossible to build a machine that can clone any given quantum state.

This is in stark contrast to the classical case, where we copy information all the time.

Proof. Suppose we have a machine with two slots: A for the quantum state |ψ⟩ to be cloned, and B in some fixed initial state |s⟩, and the machine makes a copy of the quantum state A. By the rules of quantum mechanics, the evolution U is unitary, so we have

(228)  |ψ⟩ ⊗ |s⟩ ⟶^{U} |ψ⟩ ⊗ |ψ⟩

Now suppose we have two states we wish to clone, |ψ⟩ and |φ⟩, giving

U (|ψ⟩ ⊗ |s⟩) = |ψ⟩ ⊗ |ψ⟩
U (|φ⟩ ⊗ |s⟩) = |φ⟩ ⊗ |φ⟩

Taking the inner product of these two equations, and using U^{†}U+ =:

(⟨φ| ⊗ ⟨s|) U^{†}U (|ψ⟩ ⊗ |s⟩) = (⟨φ| ⊗ ⟨φ|) (|ψ⟩ ⊗ |ψ⟩)
⟨φ|ψ⟩⟨s|s⟩ =  ⟨φ|ψ⟩⟨φ|ψ⟩
⟨φ|ψ⟩ =  (⟨φ|ψ⟩)^{2}

This has solutions if and only if ⟨φ|ψ⟩ is 0 or 1, so cloning cannot be done for general states.^{52}

□

This ends the quantum mechanics for quantum computing primer.

52There is a lot of research on what can be cloned, how much information can be cloned, etc.

Appendix D. Random Group Generation

This section is derived from Igor Pak’s online lecture notes [103]. The point of this section is to prove

Theorem D.1. Let G be a finite group. For an integer t ≥ 0, the probability that t + ⌈log |G|⌉ elements chosen uniformly at random from G will generate G is bounded by

(229)  prob\{⟨g_{1}, g_{2}, …, g_{t+⌈log |G|⌉}⟩ = G\} ≥ 1 − \frac{1}{2^{t}} for t ≥ 0

We will need some preliminaries to prove this. The idea will be to bound the number of elements that should generate G by the number needed by the “hardest” to generate group, which can be shown to be ℤ_{2}^{r}, and then estimate how many elements are needed to generate the latter group. First some notation:

Definition D.2. Given a finite group G, and elements g_{1}, g_{2}, …, g_{t} chosen uniformly at random from G, denote the probability that the g_{i} generate G by

ψ_{t}(G) = prob{⟨g_{1}, g_{2}, …, g_{t}⟩ = G}.

First a reduction to a simpler group:

Lemma D.3. Let |G| ≤ 2^{r}, r ≥ 1. Then for all t ≥ 1, ψ_{t}(G) ≥ ψ_{t}(ℤ_{2}^{r}), where ℤ_{2}^{r} is the additive group of binary r-tuples.

Proof. Fix t and a subgroup H ⊊ G. For a given sequence g_{1}, g_{2}, …, g_{t} of G, define subgroups H_{j} of G as H_{1} = ⟨g_{1}⟩, H_{2} = ⟨g_{1}, g_{2}⟩, H_{3} = ⟨g_{1}, g_{2}, g_{3}⟩, etc. Let H′_{j} be the similarly defined subgroups of ℤ_{2}^{r}. Let τ_{1}, τ_{2}, …, τ_{L} be the indices j where H_{j} ≠ H_{j−1}, and define similarly τ′_{1}, τ′_{2}, …, τ′_{R} for the H′_{j}. We will induct on |G|. When |G| = 1, the theorem is true. Let s = τ_{L−1}. We compute

prob (τ_{L} − τ_{L−1} ≤ t | H_{s} = H) = 1 − (\frac{|H|}{|G|})^{t}
≥ 1 − \frac{1}{2^{t}}
= 1 − prob (τ′_{R} − τ′_{R−1} > t)
= prob (τ′_{R} − τ′_{R−1} ≤ t)

This, combined with the induction assumption prob (τ_{L−1} ≤ t) ≥ prob (τ′_{R−1} ≤ t), gives

(230)  prob (τ_{L} ≤ t|H_{s} = H) ≥ prob (τ′_{R} ≤ t) = ψ_{t} (ℤ_{2}^{r})

This holds for any fixed t and H, so the theorem follows. □

Lemma D.4. ^{53}

ψ_{r+t}(ℤ_{2}^{r}) ≥ 1 − \frac{1}{2^{t}} for t ≥ 0

53The article [103] proved a stronger form, but this is sufficient for our purposes.

Proof. View ℤ_{2}^{r} as the r dimensional vector space over the 2 element field ℤ_{2}. Then ψ_{r+t}(ℤ_{2}^{r}) is the probability that r + t randomly chosen vectors spans the entire r dimensional space ℤ_{2}^{r}. If we write the r + t vectors as rows of a (r + t) × r matrix, then this is the probability that the matrix has column rank r. This happens if and only if all r columns are linearly independent.

The first column (which has r +t entries) is nonzero with probability (1 − \frac{1}{2^{r+t}} ). The probability that the second column is linearly independent of the first is (1 − \frac{1}{2^{r+t−1}} ), and so on. Thus for t ≥ 0 we get that

ψ_{r+t}(ℤ_{2}^{r}) = (1 − \frac{1}{2^{t+r}} ) (1 − \frac{1}{2^{t+r−1}} ) … (1 − \frac{1}{2^{t+1}} )

= 1 − \frac{1}{2^{t}} ∑_{a=1}^{r} \frac{1}{2^{a}} + \frac{1}{4^{t}} ∑_{\begin{matrix}a,b=1 \\ a≠b \end{matrix}}^{r} \frac{1}{2^{a}} \frac{1}{2^{b}} − \frac{1}{8^{t}} ∑_{\begin{matrix}a,b,c=1 \\ a≠b≠c \end{matrix}}^{r} \frac{1}{2^{a+b+c}} + …

= 1 − \frac{1}{2^{t}} (1 − \frac{1}{2^{r}} ) + \frac{1}{4^{t}} ∑_{\begin{matrix}a,b=1 \\ a≠b \end{matrix}}^{r} (\frac{1}{2^{a+b}} − ∑_{\begin{matrix}c=1 \\ c≠a≠b \end{matrix}}^{r} \frac{1}{2^{a+b+c}} ) + …

≥ 1 − \frac{1}{2^{t}} + \frac{1}{4^{t}} ∑_{a≠b} (\frac{1}{2^{a+b}} − ∑_{c=1}^{r} \frac{1}{2^{a+b+c}} ) + …

= 1 − \frac{1}{2^{t}} + \frac{1}{4^{t}} ∑_{a≠b} (\frac{1}{2^{a+b}} (1 − ∑_{c=1}^{r} \frac{1}{2^{c}} )) + …

≥ 1 − \frac{1}{2^{t}}

Note that in the lines above that the ellipses denotes a finite number of terms, which can be paired up similarly to the two terms shown, with at most one final positive term which can then be dropped in the inequality. □

Now we prove theorem D.1.

Proof. Set r = ⌈log |G|⌉, giving |G| ≤ 2^{r}. Then for t ≥ 0 we have ψ_{t+r}(G) ≥ ψ_{t+r}(ℤ_{2}^{r}) by lemma D.3, and then this is ≥ 1 − \frac{1}{2^{t}} by lemma D.4, which proves theorem D.1. □

Finally, note there are much better bounds, but this one gives the exponential performance we need for our purposes.

Appendix E. GCD Probabilities

This appendix shows the proof that the probability of the GCD of integers uniformly sampled from a fixed range becomes exponentially close to 1 in terms of the number of samples. The formal result is lemma E.3.

Unfortunately we need the next result without proof to start off the result.

Lemma E.1 ([121]). Let φ(n) be the Euler totient function^{54}. Then for any positive integer n,

(231)  |∑_{c=1}^{n} φ(c) − \frac{3n^{2}}{π^{2}} | < n ln n

where ln n is log base e.

Lemma E.2. Fix an integer n > 0. Choose two nonnegative integers a, b ≤ n uniformly at random. Then the probability that gcd(a, b) = 1 is ≥ \frac{1}{2}.

Proof. Given the uniformly randomly chosen integers a, b, the probability that max\{a, b\} = c is \frac{2c+1}{(n+1)^{2}} . This can be seen by looking at a matrix with a_{ij} entry (i, j), and counting elements, for i, j ∈ {0, 1, …, n}. Assuming c > 0, which happens with probability p_{0} = \frac{(n+1)^{2}−1}{(n+1)^{2}}, the probability that the second integer is

relatively prime to the largest one c is precisely \frac{φ(c)}{c}. So the probability p_{n} that gcd(a, b) = 1 is exactly

(232)  p_{n} = p_{0} ∑_{c=1}^{n} \frac{2c + 1}{(n + 1)^{2}} \frac{φ(c)}{c}

(233)  = \frac{n^{2} + 2n}{(n + 1)^{4}} ∑_{c=1}^{n} (2 + \frac{1}{c}) φ(c)

(234)  ≥ \frac{2n^{2} + 4n}{(n + 1)^{4}} ∑_{c=1}^{n} φ(c)

By lemma E.1 ∑ φ(c) > \frac{3n^{2}}{π^{2}} − n log n, giving

(235)  p_{n} ≥ (\frac{2n^{2} + 4n}{(n + 1)^{4}}) (\frac{3n^{2} − π^{2}n log n}{π^{2}})

Denoting the right hand side by f(n), it is easy to check f is increasing^{55} for n ≥ 4 and that f(94) > 0.5, proving the proposition for integers n ≥ 94. The remaining cases n = 1, 2, …, 93 can be easily (yet tediously) checked using equation 233. I recommend Mathematica or Maple. □

Lemma E.3. Suppose we have k ≥ 2 uniformly random samples t_{1}, t_{2}, …, t_{k} from the integers {0, 1, …, d − 1} for an integer d ≥ 2. Then

prob (gcd(t_{1}, t_{2}, …, t_{k}) = 1) ≥ 1 − (\frac{1}{2})^{k/2}

Proof. Consider the samples taken as pairs. Certainly if any pair t_{2j−1} and t_{2j} are relatively prime, then gcd(t_{1}, t_{2}, …, t_{k}) = 1. By lemma E.2 the probability that gcd(t_{2j−1}, t_{2j}) > 1 is ≤ \frac{1}{2}, so the probability that every such pair, j =

1, 2, …, ⌊k/2⌋, has gcd > 1 is ≤ (\frac{1}{2})^{⌊k/2⌋} ≤ (\frac{1}{2})^{k/2}. Thus the probability that

gcd(t_{1}, t_{2}, …, t_{k}) = 1 is ≥ 1 − (\frac{1}{2})^{k/2}. □

54For a positive integer n, φ(n) returns the number of positive integers less than n and relatively prime to n.

55lim_{n→∞} f(n) = 6/π^{2}, agreeing with Dirichlet’s 1849 theorem to that effect.

Finally we note that the above estimates and probabilities are very conservative, yet yield the essential fact that the probability of success increases exponentially with the number of trials.

References

1. S. Aaronson, Quantum lower bound for the collision problem, STOC’ 02 (Montreal, Quebec, Canada), 19-21 May 2002, quant-ph/0111102.

2. Daniel S. Abrams and Seth Lloyd, Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems, Phys.Rev.Lett. 81 (1998), 3992–3995.

3. Dorit Aharonov, Win van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev, Adiabatic quantum computation is equivalent to standard quantum computation, 2004,

quant-ph/0405098.

4. L. Babai and R. Beals, Las Vegas algorithms for matrix groups, Proc. 34th IEEE Foundations of Computer Science, 1993, pp. 427–436.

5. L. Babai and L. Rónyai, Computing irreducible representations of finite groups, Math. Comp. 55 (1990), 705–722.

6. L. Babai and E. Szemeréedi, On the complexity of matrix group problems I, Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984, pp. 229–240.

7. Adriano Barenco, Quantum physics and computers, Contemporary Physics 38 (1996), 357– 389.

8. Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John Smolin, and Harald Weinfurter, Elementary gates for quantum computation, Physical Review 52 (1995), no. 5, 3457–3467, also at

quant-ph/9503016 v1.

9. U. Baum, Existence and efficient construction of fast Fourier transforms for supersolvable groups, Comput. Complexity 1 (1991), 235–256.

10. U. Baum and M. Clausen, Some lower and upper complexity bounds for generalized Fourier transforms and their inverses, SIAM J. of Comput. 20 (1991), no. 3, 451–459.

11. , Fast Fourier transforms, BI-Verlag, 1993.

12. , Fast Fourier transforms for symmetric groups, theory and implementations, Math. Comp. 61 (1993), no. 204, 833–847.

13. U. Baum, M. Clausen, and B. Tietz, Improved upper complexity bounds for the discrete Fourier transform, AAECC 2 (1991), 35–43.

14. R. Beals, Quantum computation of Fourier transforms over symmetric groups, Proc. 29th Ann. ACM Symp. Theory of Computation (El Paso, Texas), ACM Press, 4-6 May 1997, pp. 48–53.

15. P.W. Beame, S.A. Cook, and H.J. Hoover, Log depth circuits for division and related problems, Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984, pp. 1–6.

16. Charles H. Bennett, Logical reversibility of computation, IBM J. of Research and Development 17 (1973), 525–532.

17. Charles H. Bennett, Ethan Bernstein, Giles Brassard, and Umesh Vazirani, Strengths and weaknesses of quantum computing, SIAM Journal on Computing 26 (1997), no. 5, 1510–1523.

18. Ethan Bernstein and Umesh Vazirani, Quantum complexity theory, SIAM Journal on Computing 26 (1997), no. 5, 1411–1473.

19. Thomas Beth, On the computational complexity of the general discrete Fourier transform, Theor. Comp. Sci. 51 (1987), no. 3, 331–339.

20. Thomas Beth, Markus Püschel, and Martin Rötteler, Fast quantum Fourier transforms for a class of non-abelian groups, Proc. of Applied Algebra Algebraic Algorithms, and Error-Correction Codes (AAECC-13), Springer-Verlag, 1999, volume 1719 in Lecture Notes in Computer Science, pp. 148–159.

21. M. Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp, Tight bounds on quantum searching, Proc. 4th Workshop on Physics and Computation-PhysComp, 1996, quant-ph/9605034, pp. 36–43.

22. Robert S. Boyer and J. Strother Moore, A fast string-searching algorithm, Communications of the ACM 20 (1977), no. 10, 762–772.

23. Gilles Brassard and Peter Høyer, An exact polynomial-time algorithm for Simon’s problem, Proc. 5th Israeli Symposium on Theory of Computing and Systems, IEEE Computer Society Press, 1997, quant-ph/9704027, pp. 12–33.

24. Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, Quantum amplitude amplifi-

cation, 2000, quant-ph/0005055.

25. Gilles Brassard, Peter Høyer, and Alain Tapp, Quantum counting, Lecture Notes in Computer Science 1443 (1998), 820+, quant-ph/9805082.

26. A. Robert Calderbank, Eric M. Raines, Peter W. Shor, and Neil J. Sloane, Quantum error correction and orthogonal geometry, Physical Review Letters (1997), to appear.

27. A. Robert Calderbank and Peter W. Shor, Good quantum error-correcting codes exist, Physical Review A 54 (1996), 1098–1106.

28. Kevin K. H. Cheung and Michele Mosca, Decomposing finite abelian groups, J. Quantum Inf. Comp. 1 (2001), no. 3, 26–32, quant-ph/0101004.

29. I. L. Chuang and M. A. Nielsen, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000.

30. Michael Clausen, Fast generalized Fourier transforms, Thoeret. Comput. Sci. 67 (1989), no. 1, 55–63.

31. R. Cleve,  An introduction to quantum complexity theory,  1999,

http://www.cpsc.ucalgary.ca/∼cleve/papers.html.

32. R. Cleve, E. Ekert, C. Macchiavello, and M. Mosca, Quantum algorithms revisited, Proc. Roy. Soc. Lond. A 454 (1998), 339–354.

33. R. Cleve and J. Watrous, Fast parallel circuits for the quantum Fourier transform, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, vol. 454, 2000,

http://www.cpsc.ucalgary.edu/∼jwatrous/papers/qft.ps, pp. 526–536.

34. James W. Cooley and John W. Tukey, An algorithm for the machine calculation of complex Fourier series, Math. Comput. 19 (1965), 297–301.

35. D. Coppersmith, An approximate Fourier transform useful in quantum computing, IBM Technical Report RC 19642 (1994), quant-ph/0201067.

36. Ivan Damgård, QIP Note: on the quantum Fourier transform and applications, 2001,

http://www.daimi.au.dk/∼ivan/fourier.ps.

37. David Deutsch, Quantum theory, the Church-Turing principle and the universal quantum computer, Proc. Roy. Soc. Lond. A 400 (1985), 97–117.

38. David Deutsch and Richard Jozsa, Rapid solution of problems by quantum computation, Proc. Roy. Soc. Lond. A 439 (1992), 553–558.

39. Persi Diaconis and Daniel Rockmore, Efficient computation of the Fourier transform on finite groups, J. Amer. Math. Soc. 3 (1990), no. 2, 297–332.

40. C. Dürr and P. Høyer, A quantum algorithm for finding the minimum, 1996,

quant-ph/9607014.

41. S. Egner and M. Püschel, AREP - a package for constructive representation theory, 1998.

42. A. Ekert and R. Jozsa, Quantum computation and Shor’s factoring algorithm, Rev. Modern Physics 68 (July 1996), no. 3, 733.

43. Mark Ettinger and Peter Høyer, A quantum observable for the graph isomorphism problem,

1999, quant-ph/9901029.

44. , Quantum state detection via elimination, 1999, quant-ph/9905099.

45. , On quantum algorithms for noncommutative hidden subgroups, Advances in Applied Mathematics 25 (2000), 239–251.

46. Mark Ettinger, Peter Høyer, and E. Knill, Hidden subgroup states are almost orthogonal,

1999, quant-ph/9901034.

47. , The quantum query complexity of the hidden subgroup problem is polynomial, Information Processing Letters 91 (2004), no. 1, 43–48, quant-ph/0401083.

48. Stephen Fenner and Yong Zhang, Quantum algorithms for a set of group theoretic problems,

2004, quant-ph/0408150.

49. Katalin Friedl, Gábor Ivanyos, Frédéroc Magniez, Miklos Santha, and Pranab Sen, Hidden translation and orbit coset in quantum computing, Proc. 35th ACM Symp. on Theory of Computing, 2003, pp. 1–9.

50. A. Galindo and M. A. Matrín-Delgado, Information and computation: Classical and quantum apsects, 2001, quant-ph/0112105.

51. Dmitry Gavinsky, Quantum solution to the hidden subgroup problem for poly-near-hamiltonian groups, Quantum Information and Computation 4 (2004).

52. Robert B. Griffiths and Chi-Sheng Niu, Semiclassical Fourier transform for quantum com-

putation, 1995, quant-ph/9511007.

53. M. Grigni, L. J. Schulman, M. Vazirani, and U. V. Vazirani, Quantum mechanical algorithms for the nonabelian hidden subgroup problem, Proc. 33rd ACM Symp. on Theory of Computing, 2001, pp. 68–74.

54. L. K. Grover, A fast quantum mechanical algorithm for database search, Proc. 28th Ann. ACM Symp. on Theory of Comput., 1996, pp. 212–219.

55. Lisa Hales, The quantum Fourier transform and extensions of the abelian subgroup problem, Ph.D. thesis, University of California at Berkeley, Berkeley, CA, 2002, quant-ph/0212002.

56. Lisa Hales and Sean Hallgren, Quantum Fourier sampling simplified, Proc. 31st Ann. ACM Symp. on Theory of Comput., 1999, Atlanta, Georgia, 1-4 May, pp. 330–338.

57. , An improved quantum Fourier transform algorithm and applications, Proc. 41st Ann. Symp. on Foundations of Computer Science, 2000, Redonda Beach, California, 12-14 November, pp. 515–525.

58. Sean Hallgren, Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem, Proc. 34th Ann. Symp. on Foundations of Computer Science, 2002, Montreal, Quebec, Canada, 19-21 May, pp. 515–525.

59. Sean Hallgren, A. Russell, and A. Ta-Shma, Normal subgroup reconstruction and quantum computing using group representations, Proc. 32nd Ann. ACM Symp. Theory of Computing (New York, NY), ACM Press, 2000, Portland, Oregon, 21-23 May, pp. 627–635.

60. Sean Hallgren and Wim van Dam, Efficient quantum algorithms for shifted quadratic character problems, 2000, quant-ph/0011067.

61. Sean Hallgren, Wim van Dam, and Lawrence Ip, Quantum algorithms for hidden coset problems, unpublished.

62. , Quantum algorithms for some hidden shift problems, ACM-SIAM Symposium on Discrete Algorithms (SODA) (2003), to appear.

63. Joe Harris and William Fulton, Representation theory, no. 129 in Graduate Texts in Mathematics, Springer-Verlag, New York, NY, 1991.

64. Peter Høyer, Efficient quantum transforms, 1997, quant-ph/9702028.

65. , Simplified proof of the Fourier sampling theorem, Information Processing Letters 75 (2000), no. 4, 139–143.

66. Gábor Ivanyos, Frédéroc Magniez, and Miklos Santha, Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem, Proc. 13th Ann. ACM Symp. on Parallel Algorithms and Architectures (New York, NY), ACM Press, 2001, Heraklion, Crete Island, Greece, 4-6 July, pp. 263–270.

67. G. James and Adalbert Kerber, The representation theory of the symmetric group, Cambridge University Press, 1982.

68. R. Jozsa, Quantum algorithms and the Fourier transform, Proc. Royal Soc. London Series A 454 (1998), no. 1969, 323–337.

69. , Quantum factoring, discrete logarithms and the hidden subgroup problem, 2000,

quant-ph/0012084.

70. , Notes on Hallgren’s efficient quantum algorithm for solving Pell’s equation, 2003,

quant-ph/0302134.

71. H. W. Lenstra Jr. and C. Pomerance, A rigorous time bound for factoring integers, Journal of the AMS 5 (1992), no. 2, 483–516.

72. M. Karpovsky, Fast Fourier transforms on finite abelian groups, IEEE Trans. Comput. 26 (1977), no. 10, 1028–1030.

73. Julia Kempe, Quantum random walks hit exponentially faster, 2002, quant-ph/0205083.

74. Julia Kempe and Aner Shalev, The hidden subgroup problem and permutation group theory,

2004, quant-ph/0406046.

75. Adalbert Kerber, Representations of permutation groups I, vol. Lecture Notes in Mathematics 240, Springer-Verlag, Berlin, 1971.

76. , Representations of permutation groups II, vol. Lecture Notes in Mathematics 495, Springer-Verlag, Berlin, 1975.

77. Alexi Yu. Kitaev, Quantum measurements and the Abelian stabilizer problem, 1995,

quant-ph/9511026.

78. , Quantum computations: algorithms and error correction, Russ. Math. Surv. 52 (1997), no. 6, 1191–1249.

79. Donald Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition), Addison-Wesley, 1997, ISBN: 0201896842.

80. Donald Knuth, James Morris, and Vaughan Pratt, Fast pattern matching in strings, SIAM Journal on Computing 6 (1977), no. 2, 323–350.

81. Johannes Köbler, Uwe Schöning, and Jacobo Torán, The graph isomorphism problem: Its structural complexity, Birkhauser Boston Inc., Boston, MA, 1993.

82. Greg Kuperberg, A subexponential-time algorithm for the dihedral hidden subgroup problem,

2003, quant-ph/0302112.

83. Serge Lang, Algebra, Addison-Wesley Publishing, 1993, ISBN 0-201-55540-9.

84. S. J. Lomonaco and L.H. Kauffman, Quantum hidden subgroup problems: A mathematical perspective, 2002, quant-ph/0201095.

85. , Continuous quantum hidden subgroup algorithms, 2003, quant-ph/0304084.

86. Samuel J. Lomonaco (ed.), Quantum computation: A grand mathematical challenge for the twenty-first century and the millenium, AMS, Providence, RI., 2002, PSAPM 58.

87. Chris Lomont, Quantum convolution and quantum correlation algorithms are physically im-

possible, 2003, quant-ph/0309070.

88. , A quantum Fourier transform algorithm, 2004, quant-ph/0404060.

89. David K. Maslen and Daniel N. Rockmore, Separation of variables and the efficient computation of Fourier transforms on finite groups, II, in preparation.

90. , Adapted diameters and the efficient computation of Fourier transforms on finite groups, Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, California, 22-24 January), 1995, pp. 253–262.

91. , Separation of variables and the computation of Fourier transforms on finite groups, I, J. Amer. Math. Soc. 10 (1997), no. 1, 169–214.

92. , Generalized FFT’s: A survey of some recent results, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 28, ACM, 1997(1995), June 7-10, pp. 183–237.

93. , The Cooley-Tukey FFT and group theory, Notices Amer. Math. Soc. 48 (2001), no. 10, 1151–1160.

94. Rudolf Mathon, A note on the graph isomorphism problem, Information Processing Letters 8 (1979), 131–132.

95. G. L. Miller, Graph Isomorphism, general remarks, Journal of Computer and System Sciences 18 (1979), 128–142.

96. Christopher Moore, Daniel Rockmore, and Alexander Russell, Generic quantum FFTs,

http://www.cs.dartmouth.edu/∼rockmore/qfftcamera.pdf, 2004, SODA 2004, to appear.

97. Christopher Moore, Daniel Rockmore, Alexander Russell, and Leonard Schulman, The hidden subgroup problem in affine groups: Basis selection in Fourier sampling, quant-ph/0211124, 2002, SODA 2004, to appear.

98. Michele Mosca, Quantum computer algorithms, Ph.D. thesis, Wolfson College, University of Oxford, Oxford, United Kingdom, 1999,

www.cacr.math.uwaterloo.ca/∼mmosca/moscathesis.ps.

99. Michele Mosca and Artur Ekert, The hidden subgroup problem and eigenvalue estimation on a quantum computer, QCQS: NASA International Conference on Quantum Computing and Quantum Communications, LNCS, 1998.

100. Michele Mosca and Christof Zalka, Exact quantum Fourier transforms and discrete logarithm algorithms, 2003, quant-ph/0301093.

101. Román Orús, José I. Latorre, and Miguel A. Martín-Delgado, Natural majorization of the quantum Fourier transformation in phase-estimation algorithms, 2003, quant-ph/0206134.

102. , Systematic analysis of majorization in quantum algorithms, 2003,

quant-ph/0212094.

103. Igor Pak, 18.317 combinatorics, probability and computations on groups (fall 2001), 2001,

http://www-math.mit.edu/∼pak/courses/pg.html.

104. Arun K. Pati and Samuel L. Braustein, Deutsch-Jozsa algorithm for continuous variables,

2002, quant-ph/0207108.

105. Arun K. Pati, Samuel L. Braustein, and Seth Lloyd, Quantum searching with continuous

variables, 2000, quant-ph/0002082.

106. H. Ramesh and V. Vinay, String matching in Õ(\sqrt{n}+\sqrt{m}) quantum time, Journal of Discrete Algorithms 2 (2001), no. 1, quant-ph/0011049.

107. O. Regev, Quantum computation and lattice problems, Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS), 2002.

108. Daniel N. Rockmore, Fast Fourier analysis for abelian group extensions, Advances in Applied Mathematics 11 (1990), 164–204.

109. , Efficient computation of Fourier inversion for finite groups, J. of the ACM 41 (1994), no. 1, 31–66.

110. , Fast Fourier transforms for wreath products, J. Applied and Computational Harmonic Analysis 2 (1995), 279–292.

111. Joseph Rotman, An introduction to the theory of groups, vol. Number 148 in Graduate Texts in Mathematics, Springer-Verlag, 1995.

112. Martin Rötteler and Thomas Beth, Polynomial time solution to the hidden subgroup problem for a class of non-abelian groups, 1998, quant-ph/9812070.

113. Jean-Pierre Serre, Linear representations on finite groups, Springer-Verlag, 1977.

114. P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, Proceedings, 35th Annual Symposium on Fundamentals of Comp. Science (FOCS), 1994, pp. 124–134.

115. , Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Computing 26 (1997), no. 5, 1484–1509.

116. , Introduction to quantum algorithms, AMS PSAPM/58, 2002, pp. 124–134.

117. Barry Simon, Representations of finite and compact groups, vol. 10 in Graduate Studies in Mathematics, American Mathematical Society, 1996.

118. Daniel Simon, On the power of quantum computation, Proceedings of the 35th Annual Symposium on Foundations of Computer Science (Los Alamitos, CA), Institute of Electrical and Electronic Engineers Computer Society Press, 1994, citeseer.nj.nec.com/article/simon94power.html, pp. 116–123.

119. , On the power of quantum computation, SIAM J. Computing 26 (1997), no. 5, 1474–1483.

120. Arne Storjohann, Near optimal algorithms for computing smith normal forms of integer matrices, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, ACM Press, 1996, pp. 267–274.

121. R. Tambs-Lyche, Kongelige norske videnskabers skelskabs forhandlinger, vol. 9, Trondhjem, Norway, 1936.

122. Audrey Terras, Fourier analysis on finite goups and applications, no. 43 in London Mathematical Society Student Texts, Cambridge University Press, 1999.

123. W. van Dam, Michele Mosca, and U. Vazirani, How powerful is adiabatic quantum compu-

tation, 2002, quant-ph/0206003.

124. Wim van Dam, Quantum algorithms for weighting matrices and quadratic residues, 2000,

quant-ph/0008059.

125. J. Waltrous, Succinct quantum proofs of properties of finite groups, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000, pp. 537–546.

126. , Quantum algorithms for solvable groups, Proceedings of the 33rd ACM Symposium on Theory of Computing, 2001, pp. 60–67.

127. W. K. Wootters and W. H. Zurek, A single quantum cannot be cloned, Nature 299 (1982), 802–803.

128. Andrew Chi-Chih Yao, Quantum circuit complexity, Proc. 34th Ann. Symp. on Found. of Comp. Sci., 1996, pp. 352–361.

129. Christof Zalka, On a particular non-abelian hidden subgroup problem, 1999,

http://qso.lanl.gov/∼zalka/QC/QC.html.