The computational power of normalizer circuits over black-box groups

Abstract

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.

40 pages + appendices

References in corpus (12)

• Quantum computation over continuous variables
• On the Power of One Bit of Quantum Information
• Efficient Classical Simulation of Continuous Variable Quantum Information Processes
• Quantum algorithms for algebraic problems
• Classical simulation of noninteracting-fermion quantum circuits
• Instantaneous Quantum Computation
• Fermionic Linear Optics and Matchgates
• Efficient Classical Simulation of Optical Quantum Circuits
• Commuting quantum circuits: efficient classical simulations versus hardness results
• Quantum Complexity: restrictions on algorithms and architectures
• Quantum algorithms for problems in number theory, algebraic geometry, and group theory
• Normalizer circuits and a Gottesman-Knill theorem for infinite-dimensional systems

Cited by in corpus (4)

• Contextuality as a resource for models of quantum computation on qubits
• Normalizer Circuits and Quantum Computation
• Normalizer circuits and a Gottesman-Knill theorem for infinite-dimensional systems
• Abelian Hypergroups and Quantum Computation