Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1510.08134 · Springer proceedings in physics

Towards a Quantum Sampling Theory: The Case of Finite Groups

Antonio G. García, Miguel Angel Hernández-Medina, Alberto Ibort

Published Jan 1, 2019• 3 citations
arXivHTMLPDF
DOI
10.1007/978-3-030-24748-5_11

Related papers

Finite groups and quantum theory

D. B. Chesnut

•Jan 1, 1974•13 citations

The hidden subgroup problem and permutation group theory

Julia Kempe, Aner Shalev

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/0406046•Symposium on Discrete Algorithms•Jun 8, 2004•44 citations

Quantum Mechanics on Finite Groups

Stanley Gudder

Foundations of Physics•May 11, 2006•2 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.

arXiv:2309.07090•Physical review. D/Physical review. D.•Feb 15, 2024•9 citations

Quantum Algorithms for a Set of Group Theoretic Problems

Stephen Fenner, Yong Zhang

Lecture notes in computer science•Jan 1, 2005•6 citations

Quantum Walks Advantage on the Dihedral Group for Uniform Sampling Problem

Shyam Dhamapurkar, Yu–Hang Dang, Saniya Wagh +1 more

Random walk algorithms, including sampling and approximations, have played a significant role in statistical physics and theoretical computer science. Mixing through walks is the process for a Markov chain to approximate a stationary distribution for a group. Quantum walks have shown potential advantages in mixing time over the classical case but lack general proof in the finite group case. Here, we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group D2n for odd n, generated by the smallest inverse closed symmetric subset. We present a significant finding that, in contrast to the classical mixing time on these Cayley graphs, which typically takes at least order Ω(n2log(1/2ε)), the continuous-time quantum walk mixing time on D2n is of order Ω($n(log n)$5log(1/ε)), achieving a quadratic improvement over the classical case. Our paper advances the general understanding of quantum walk mixing on Cayley graphs, highlighting the improved mixing time achieved by continuous-time quantum walks on D2n. This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.

International Conference on Quantum Communications, Networking, and Computing (QCNC)•Jul 1, 2024•0 citations
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.
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 D4{D}_{4}D4​ in (2+12+12+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.
Random walk algorithms, including sampling and approximations, have played a significant role in statistical physics and theoretical computer science. Mixing through walks is the process for a Markov chain to approximate a stationary distribution for a group. Quantum walks have shown potential advantages in mixing time over the classical case but lack general proof in the finite group case. Here, we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group D2n for odd n, generated by the smallest inverse closed symmetric subset. We present a significant finding that, in contrast to the classical mixing time on these Cayley graphs, which typically takes at least order Ω(n2log(1/2ε)), the continuous-time quantum walk mixing time on D2n is of order Ω($n(log n)$5log(1/ε)), achieving a quadratic improvement over the classical case. Our paper advances the general understanding of quantum walk mixing on Cayley graphs, highlighting the improved mixing time achieved by continuous-time quantum walks on D2n. This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.