02194nas a2200133 4500008004100000245007300041210006800114260001500182520175300197100002301950700002401973700002601997856003702023 2014 eng d00aThe computational power of normalizer circuits over black-box groups0 acomputational power of normalizer circuits over blackbox groups c2014/09/163 a This work presents a precise connection between Clifford circuits, Shor's
factoring algorithm and several other famous quantum algorithms with
exponential quantum speed-ups for solving Abelian hidden subgroup problems. We
show that all these different forms of quantum computation belong to a common
new restricted model of quantum operations that we call \emph{black-box
normalizer circuits}. To define these, we extend the previous model of
normalizer circuits [arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208], which
are built of quantum Fourier transforms, group automorphism and quadratic phase
gates associated to an Abelian group $G$. In previous works, the group $G$ is
always given in an explicitly decomposed form. In our model, we remove this
assumption and allow $G$ to be a black-box group. While standard normalizer
circuits were shown to be efficiently classically simulable
[arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208], we find that normalizer
circuits are powerful enough to factorize and solve classically-hard problems
in the black-box setting. We further set upper limits to their computational
power by showing that decomposing finite Abelian groups is complete for the
associated complexity class. In particular, solving this problem renders
black-box normalizer circuits efficiently classically simulable by exploiting
the generalized stabilizer formalism in
[arXiv:1201.4867v1,arXiv:1210.3637,arXiv:1409.3208]. Lastly, we employ our
connection to draw a few practical implications for quantum algorithm design:
namely, we give a no-go theorem for finding new quantum algorithms with
black-box normalizer circuits, a universality result for low-depth normalizer
circuits, and identify two other complete problems.
1 aBermejo-Vega, Juan1 aLin, Cedric, Yen-Yu1 aVan den Nest, Maarten uhttp://arxiv.org/abs/1409.4800v102350nas a2200133 4500008004100000245009000041210006900131260001500200520189100215100002302106700002402129700002602153856003702179 2014 eng d00aNormalizer circuits and a Gottesman-Knill theorem for infinite-dimensional systems
0 aNormalizer circuits and a GottesmanKnill theorem for infinitedim c2014/09/103 a $\textit{Normalizer circuits}$ [1,2] are generalized Clifford circuits that
act on arbitrary finite-dimensional systems $\mathcal{H}_{d_1}\otimes ...
\otimes \mathcal{H}_{d_n}$ with a standard basis labeled by the elements of a
finite Abelian group $G=\mathbb{Z}_{d_1}\times... \times \mathbb{Z}_{d_n}$.
Normalizer gates implement operations associated with the group $G$ and can be
of three types: quantum Fourier transforms, group automorphism gates and
quadratic phase gates. In this work, we extend the normalizer formalism [1,2]
to infinite dimensions, by allowing normalizer gates to act on systems of the
form $\mathcal{H}_\mathbb{Z}^{\otimes a}$: each factor $\mathcal{H}_\mathbb{Z}$
has a standard basis labeled by $\textit{integers}$ $\mathbb{Z}$, and a Fourier
basis labeled by $\textit{angles}$, elements of the circle group $\mathbb{T}$.
Normalizer circuits become hybrid quantum circuits acting both on continuous-
and discrete-variable systems. We show that infinite-dimensional normalizer
circuits can be efficiently simulated classically with a generalized
$\textit{stabilizer formalism}$ for Hilbert spaces associated with groups of
the form $\mathbb{Z}^a\times \mathbb{T}^b \times
\mathbb{Z}_{d_1}\times...\times \mathbb{Z}_{d_n}$. We develop new techniques to
track stabilizer-groups based on normal forms for group automorphisms and
quadratic functions. We use our normal forms to reduce the problem of
simulating normalizer circuits to that of finding general solutions of systems
of mixed real-integer linear equations [3] and exploit this fact to devise a
robust simulation algorithm: the latter remains efficient even in pathological
cases where stabilizer groups become infinite, uncountable and non-compact. The
techniques developed in this paper might find applications in the study of
fault-tolerant quantum computation with superconducting qubits [4,5].
1 aBermejo-Vega, Juan1 aLin, Cedric, Yen-Yu1 aVan den Nest, Maarten uhttp://arxiv.org/abs/1409.3208v2