We employ concepts and tools from the theory of finite permutation groups in order to analyse the Hidden Subgroup Problem via Quantum Fourier Sampling (QFS) for the symmetric group. We show that under very general conditions both the weak and the random-strong form (strong form with random choices of basis) of QFS fail to provide any advantage over classical exhaustive search. In particular we give a complete characterisation of polynomial size subgroups, and of primitive subgroups, that can be distinguished from the identity subgroup with the above methods. Furthermore, assuming a plausible group theoretic conjecture for which we give supporting evidence, we show that weak and random-strong QFS for the symmetric group have no advantage whatsoever over classical search.We employ concepts and tools from the theory of finite permutation groups in order to analyse the Hidden Subgroup Problem via Quantum Fourier Sampling (QFS) for the symmetric group. We show that under very general conditions both the weak and the random-strong form (strong form with random choices of basis) of QFS fail to provide any advantage over classical exhaustive search. In particular we give a complete characterisation of polynomial size subgroups, and of primitive subgroups, that can be distinguished from the identity subgroup with the above methods. Furthermore, assuming a plausible group theoretic conjecture for which we give supporting evidence, we show that weak and random-strong QFS for the symmetric group have no advantage whatsoever over classical search.

arXiv:quant-ph/0406046Symposium on Discrete AlgorithmsJun 8, 200442 citations

Quantum computation of thermal averages for a non-Abelian D4 lattice gauge theory via quantum Metropolis sampling

Edoardo Ballini, Giuseppe Clemente, Massimo D’Elia +2 more

In this paper, we show the application of the quantum Metropolis sampling (QMS) algorithm to a toy gauge theory with discrete non-Abelian gauge group ${D}_{4}$ in ( $2+1$ )-dimensions, discussing in general how some components of hybrid quantum-classical algorithms should be adapted in the case of gauge theories. In particular, we discuss the construction of random unitary operators which preserve gauge invariance and act transitively on the physical Hilbert space, constituting an ergodic set of quantum Metropolis moves between gauge invariant eigenspaces, and introduce a protocol for gauge invariant measurements. Furthermore, we show how a finite resolution in the energy measurements distorts the energy and plaquette distribution measured via QMS, and propose a heuristic model that takes into account part of the deviations between numerical results and exact analytical results, whose discrepancy tends to vanish by increasing the number of qubits used for the energy measurements.In this paper, we show the application of the quantum Metropolis sampling (QMS) algorithm to a toy gauge theory with discrete non-Abelian gauge group ${D}_{4}$ in ($2+1$)-dimensions, discussing in general how some components of hybrid quantum-classical algorithms should be adapted in the case of gauge theories. In particular, we discuss the construction of random unitary operators which preserve gauge invariance and act transitively on the physical Hilbert space, constituting an ergodic set of quantum Metropolis moves between gauge invariant eigenspaces, and introduce a protocol for gauge invariant measurements. Furthermore, we show how a finite resolution in the energy measurements distorts the energy and plaquette distribution measured via QMS, and propose a heuristic model that takes into account part of the deviations between numerical results and exact analytical results, whose discrepancy tends to vanish by increasing the number of qubits used for the energy measurements.

Physical review. D/Physical review. D.Feb 15, 20246 citations

Quantum algorithms in group theory

M Batty, SL Braunstein, Andrew J. Duncan +1 more

Dec 31, 20030 citations

Quantum Computation of Thermal Averages for a Non-Abelian $D_4$ Lattice Gauge Theory via Quantum Metropolis SamplingQuantum Computation of Thermal Averages for a Non-Abelian $D_4$ Lattice Gauge Theory via Quantum Metropolis Sampling

Edoardo Ballini, Giuseppe Clemente, Massimo D’Elia +2 more

In this paper, we show the application of the Quantum Metropolis Sampling (QMS) algorithm to a toy gauge theory with discrete non-Abelian gauge group $D_4$ in (2+1)-dimensions, discussing in general how some components of hybrid quantum-classical algorithms should be adapted in the case of gauge theories. In particular, we discuss the construction of random unitary operators which preserve gauge invariance and act transitively on the physical Hilbert space, constituting an ergodic set of quantum Metropolis moves between gauge invariant eigenspaces, and introduce a protocol for gauge invariant measurements. Furthermore, we show how a finite resolution in the energy measurements distorts the energy and plaquette distribution measured via QMS, and propose a heuristic model that takes into account part of the deviations between numerical results and exact analytical results, whose discrepancy tends to vanish by increasing the number of qubits used for the energy measurements.In this paper, we show the application of the Quantum Metropolis Sampling (QMS) algorithm to a toy gauge theory with discrete non-Abelian gauge group $D_4$ in (2+1)-dimensions, discussing in general how some components of hybrid quantum-classical algorithms should be adapted in the case of gauge theories. In particular, we discuss the construction of random unitary operators which preserve gauge invariance and act transitively on the physical Hilbert space, constituting an ergodic set of quantum Metropolis moves between gauge invariant eigenspaces, and introduce a protocol for gauge invariant measurements. Furthermore, we show how a finite resolution in the energy measurements distorts the energy and plaquette distribution measured via QMS, and propose a heuristic model that takes into account part of the deviations between numerical results and exact analytical results, whose discrepancy tends to vanish by increasing the number of qubits used for the energy measurements.

arXiv:2309.07090Physical review. D/Physical review. D.Sep 13, 20231 citation

Quantum Algorithms in Group Theory

M Batty, SL Braunstein, Andrew Duncan +1 more

Dec 31, 20040 citations

In this paper, we show the application of the quantum Metropolis sampling (QMS) algorithm to a toy gauge theory with discrete non-Abelian gauge group

{D}_{4}

in (

2+1

)-dimensions, discussing in general how some components of hybrid quantum-classical algorithms should be adapted in the case of gauge theories. In particular, we discuss the construction of random unitary operators which preserve gauge invariance and act transitively on the physical Hilbert space, constituting an ergodic set of quantum Metropolis moves between gauge invariant eigenspaces, and introduce a protocol for gauge invariant measurements. Furthermore, we show how a finite resolution in the energy measurements distorts the energy and plaquette distribution measured via QMS, and propose a heuristic model that takes into account part of the deviations between numerical results and exact analytical results, whose discrepancy tends to vanish by increasing the number of qubits used for the energy measurements.

Quantum Computation of Thermal Averages for a Non-Abelian

D_4

Lattice Gauge Theory via Quantum Metropolis Sampling

In this paper, we show the application of the Quantum Metropolis Sampling (QMS) algorithm to a toy gauge theory with discrete non-Abelian gauge group

D_4

in (2+1)-dimensions, discussing in general how some components of hybrid quantum-classical algorithms should be adapted in the case of gauge theories. In particular, we discuss the construction of random unitary operators which preserve gauge invariance and act transitively on the physical Hilbert space, constituting an ergodic set of quantum Metropolis moves between gauge invariant eigenspaces, and introduce a protocol for gauge invariant measurements. Furthermore, we show how a finite resolution in the energy measurements distorts the energy and plaquette distribution measured via QMS, and propose a heuristic model that takes into account part of the deviations between numerical results and exact analytical results, whose discrepancy tends to vanish by increasing the number of qubits used for the energy measurements.