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:0708.2560 · Physical Review A

Application of quantum algorithms to the study of permutations and group automorphisms

Marianna C. Bonanome, Mark S. Hillery, Vladimír Bužek

Published Jul 24, 2007• 3 citations
arXivHTMLPDF

Abstract

We discuss three applications of efficient quantum algorithms to determining properties of permutations and group automorphisms. The first uses the Bernstein-Vazirani algorithm to determine an unknown homomorphism from ${Z}_{p\ensuremath{-}1}^{m}$ to $\mathit{Aut}({Z}_{p})$ where $p$ is prime. The remaining two make use of modifications of the Grover search algorithm. The first finds the fixed point of a permutation or an automorphism (assuming it has only one besides the identity). It can be generalized to find cycles of a specified size for permutations or orbits of a specified size for automorphisms. The second finds which of a set of permutations or automorphisms maps one particular element of a set or group onto another. This has relevance to the conjugacy problem for groups. We show how two of these algorithms can be implemented via programmable quantum processors. This approach opens new perspectives in quantum information processing when both the data and the programs are represented by states of quantum registers. In particular, quantum programs that specify control over data can be treated using methods of quantum information theory.

DOI
10.1103/physreva.76.012324

Related papers

Quantum algorithms for fixed points and invariant subgroups

Marianna C. Bonanome, Stephen Majewicz

In this paper, we apply quantum algorithms to solve problems concerning fixed points and invariant subgroups of automorphisms. These efficient algorithms invoke a quantum algorithm which computes the intersection of multiple unsorted multisets whose elements originate from the same set. This intersection algorithm is an application of the Grover search procedure.

journal of Groups complexity cryptology•Jan 1, 2011•0 citations

Computations in Finite Groups and Quantum Physics

Vladimir V. Kornyak

Mathematical core of quantum mechanics is the theory of unitary representations of symmetries of physical systems. We argue that quantum behavior is a natural result of extraction of "observable" information about systems containing "unobservable" elements in their descriptions. Since our aim is physics where the choice between finite and infinite descriptions can not have any empirical consequences, we consider the problem in the finite background. Besides, there are many indications from observations - from the lepton mixing data, for example - that finite groups underly phenomena in particle physics at the deep level. The "finite" approach allows to reduce any quantum dynamics to the simple permutation dynamics, and thus to express quantum observables in terms of permutation invariants of symmetry groups and their integer characteristics such as sizes of conjugate classes, sizes of group orbits, class coefficients, dimensions of representations. Our study has been accompanied by computations with finite groups, their representations and invariants. We have used both our C implementation of algorithms for working with groups and computer algebra system GAP.

arXiv:1106.2759•May 24, 2011•0 citations

Quantum Programmable Reflections

Eddie Schoute, Dmitry Grinko, Yiğit Subaşı +1 more

Similar to a classical processor, which is an algorithm for reading a program and executing its instructions on input data, a universal programmable quantum processor is a fixed quantum channel that reads a quantum program $\lvertψ_{U}\rangle$ that causes the processor to approximately apply an arbitrary unitary $U$ to a quantum data register. The present work focuses on a class of simple programmable quantum processors for implementing reflection operators, i.e. $U = e^{i π\lvertψ\rangle\langleψ\rvert}$ for an arbitrary pure state $\lvertψ\rangle$ of finite dimension $d$. Unlike quantum programs that assume query access to $U$, our program takes the form of independent copies of the state to be reflected about $\lvertψ_U\rangle = \lvertψ\rangle^{\otimes n}$. We then identify the worst-case optimal algorithm among all processors of the form $\text{tr}_{\text{Program}}[V (\lvertϕ\rangle\langleϕ\rvert \otimes (\lvertψ\rangle\langleψ\rvert)^{\otimes n}) V^\dagger]$ where the algorithm $V$ is a unitary linear combination of permutations. By generalizing these algorithms to processors for arbitrary-angle rotations, $e^{i α\lvertψ\rangle\langleψ\rvert}$ for $α\in \mathbb R$, we give a construction for a universal programmable processor with better scaling in $d$. For programming reflections, we obtain a tight analytical lower bound on the program dimension by bounding the Holevo information of an ensemble of reflections applied to an entangled probe state. The lower bound makes use of a block decomposition of the uniform ensemble of reflected states with respect to irreps of the partially transposed permutation matrix algebra, and two representation-theoretic conjectures based on extensive numerical evidence.

arXiv:2411.03648•Nov 6, 2024•7 citations

FPGA Acceleration of Quantum Circuit Primitives: Fixed-Point Microcoded Design and CPU Comparison

Shahriar Rizvi, Md. Nazrul Islam Mondal

Quantum algorithms such as the Quantum Fourier Transform (QFT), Grover’s Search, the Bernstein–Vazirani (BV) algorithm, and Bell-state generation are computationally intensive to emulate on classical processors due to the exponential growth of state vectors. This work presents a fixed-point, microcoded FPGA accelerator that achieves deterministic timing, near-unit fidelity, and linear scalability up to 4 qubits. The design features a microcoded control plane with pairwise and diagonal opcodes, fixed-point complex arithmetic, and subspace-gated execution (qubit0= LSB). We benchmark QFT(2–4), BV(2–4), Grover(4), and Bell(2) at 100 MHz and compare against equivalent CPU state-vector simulations. Across all algorithms, the FPGA demonstrates consistent latency reduction: QFT: 88×–154× (98.9–99.4% faster), BV: 54×–90× (98.1–98.9% faster), Bell: 282× (99.6% faster), and Grover-4: 14.2× (93.0% faster). Fidelity is near-unit for all programs except a single BV-2 run that yields 0.875 ; QFT, Bell, BV-3, BV-4 and Grover-4 achieve 1.000. Latency scales linearly with qubit count—growing by ~1.8× per additional qubit for QFT and ~1.6× for BV—confirming the deterministic and cycle-predictable nature of the microcoded architecture. Results reflect 100 MHz RTL simulation (Verilator); we report synthesis resources and post-P&R Fmax, and express speedups normalized to 100 MHz. These results show that even a modest FPGA can outperform our CPU state-vector baseline on small-n kernels while preserving deterministic, cycle-accurate timing for small-to-medium quantum workloads through spatial parallelism and hardware-level determinism.

International Conference on Electrical, Computer & Telecommunication Engineering (ICECTE)•Jan 29, 2026•0 citations

Conjugated operators in quantum algorithms

Peter Høyer

This paper addresses the question of understanding quantum algorithms in terms of unitary operators. Many quantum algorithms can be expressed as applications of operators formed by conjugating so-called classical operators. The operators that are used for conjugation are determined by the problem and any additional structure possessed by the Hilbert space that is acted upon. We prove many commutative laws for these different operators, and we use those to phrase and analyze old and new problems and algorithms. As an example, we review the Abelian subgroup problem. We then introduce the problem of determining a group homomorphism, and we give classical and quantum algorithms for it. We also generalize Deutsch's problem and improve the previous best algorithms for earlier generalizations of it.

Physical Review A•May 1, 1999•35 citations

Two-Qutrit Quantum Algorithms on a Programmable Superconducting Processor

Tanay Roy, Ziqian Li, Eliot Kapit +1 more

Processing quantum information using quantum three-level systems or qutrits as the fundamental unit is an alternative to contemporary qubit-based architectures with the potential to provide significant computational advantages. We demonstrate a fully programmable two-qutrit quantum processor by utilizing the third energy eigenstates of two transmons. We develop a parametric coupler to achieve excellent connectivity in the nine-dimensional Hilbert space enabling efficient implementations of two-qutrit gates. We characterize our processor by realizing several algorithms like Deutsch-Jozsa, Bernstein-Vazirani, and Grover's search. Our hardware-efficient protocols allow us to show that two stages of Grover's amplification can improve the success rates of an unstructured search with quantum advantage. Our results pave the way for building fully programmable ternary quantum processors using transmons as building blocks for a universal quantum computer.

arXiv:2211.06523•Physical Review Applied•Jun 7, 2023•77 citations
We discuss three applications of efficient quantum algorithms to determining properties of permutations and group automorphisms. The first uses the Bernstein-Vazirani algorithm to determine an unknown homomorphism from Zp\ensuremath−1m{Z}_{p\ensuremath{-}1}^{m}Zp\ensuremath−1m​ to Aut(Zp)\mathit{Aut}({Z}_{p})Aut(Zp​) where ppp is prime. The remaining two make use of modifications of the Grover search algorithm. The first finds the fixed point of a permutation or an automorphism (assuming it has only one besides the identity). It can be generalized to find cycles of a specified size for permutations or orbits of a specified size for automorphisms. The second finds which of a set of permutations or automorphisms maps one particular element of a set or group onto another. This has relevance to the conjugacy problem for groups. We show how two of these algorithms can be implemented via programmable quantum processors. This approach opens new perspectives in quantum information processing when both the data and the programs are represented by states of quantum registers. In particular, quantum programs that specify control over data can be treated using methods of quantum information theory.
Mathematical core of quantum mechanics is the theory of unitary representations of symmetries of physical systems. We argue that quantum behavior is a natural result of extraction of "observable" information about systems containing "unobservable" elements in their descriptions. Since our aim is physics where the choice between finite and infinite descriptions can not have any empirical consequences, we consider the problem in the finite background. Besides, there are many indications from observations - from the lepton mixing data, for example - that finite groups underly phenomena in particle physics at the deep level. The "finite" approach allows to reduce any quantum dynamics to the simple permutation dynamics, and thus to express quantum observables in terms of permutation invariants of symmetry groups and their integer characteristics such as sizes of conjugate classes, sizes of group orbits, class coefficients, dimensions of representations. Our study has been accompanied by computations with finite groups, their representations and invariants. We have used both our C implementation of algorithms for working with groups and computer algebra system GAP.
Similar to a classical processor, which is an algorithm for reading a program and executing its instructions on input data, a universal programmable quantum processor is a fixed quantum channel that reads a quantum program ∣ψU⟩\lvertψ_{U}\rangle∣ψU​⟩ that causes the processor to approximately apply an arbitrary unitary UUU to a quantum data register. The present work focuses on a class of simple programmable quantum processors for implementing reflection operators, i.e. U=eiπ∣ψ⟩⟨ψ∣U = e^{i π\lvertψ\rangle\langleψ\rvert}U=eiπ∣ψ⟩⟨ψ∣ for an arbitrary pure state ∣ψ⟩\lvertψ\rangle∣ψ⟩ of finite dimension ddd. Unlike quantum programs that assume query access to UUU, our program takes the form of independent copies of the state to be reflected about ∣ψU⟩=∣ψ⟩⊗n\lvertψ_U\rangle = \lvertψ\rangle^{\otimes n}∣ψU​⟩=∣ψ⟩⊗n. We then identify the worst-case optimal algorithm among all processors of the form trProgram[V(∣ϕ⟩⟨ϕ∣⊗(∣ψ⟩⟨ψ∣)⊗n)V†]\text{tr}_{\text{Program}}[V (\lvertϕ\rangle\langleϕ\rvert \otimes (\lvertψ\rangle\langleψ\rvert)^{\otimes n}) V^\dagger]trProgram​[V(∣ϕ⟩⟨ϕ∣⊗(∣ψ⟩⟨ψ∣)⊗n)V†] where the algorithm VVV is a unitary linear combination of permutations. By generalizing these algorithms to processors for arbitrary-angle rotations, eiα∣ψ⟩⟨ψ∣e^{i α\lvertψ\rangle\langleψ\rvert}eiα∣ψ⟩⟨ψ∣ for α∈Rα\in \mathbb Rα∈R, we give a construction for a universal programmable processor with better scaling in ddd. For programming reflections, we obtain a tight analytical lower bound on the program dimension by bounding the Holevo information of an ensemble of reflections applied to an entangled probe state. The lower bound makes use of a block decomposition of the uniform ensemble of reflected states with respect to irreps of the partially transposed permutation matrix algebra, and two representation-theoretic conjectures based on extensive numerical evidence.
Quantum algorithms such as the Quantum Fourier Transform (QFT), Grover’s Search, the Bernstein–Vazirani (BV) algorithm, and Bell-state generation are computationally intensive to emulate on classical processors due to the exponential growth of state vectors. This work presents a fixed-point, microcoded FPGA accelerator that achieves deterministic timing, near-unit fidelity, and linear scalability up to 4 qubits. The design features a microcoded control plane with pairwise and diagonal opcodes, fixed-point complex arithmetic, and subspace-gated execution (qubit0= LSB). We benchmark QFT(2–4), BV(2–4), Grover(4), and Bell(2) at 100 MHz and compare against equivalent CPU state-vector simulations. Across all algorithms, the FPGA demonstrates consistent latency reduction: QFT: 88×–154× (98.9–99.4% faster), BV: 54×–90× (98.1–98.9% faster), Bell: 282× (99.6% faster), and Grover-4: 14.2× (93.0% faster). Fidelity is near-unit for all programs except a single BV-2 run that yields 0.875 ; QFT, Bell, BV-3, BV-4 and Grover-4 achieve 1.000. Latency scales linearly with qubit count—growing by ~1.8× per additional qubit for QFT and ~1.6× for BV—confirming the deterministic and cycle-predictable nature of the microcoded architecture. Results reflect 100 MHz RTL simulation (Verilator); we report synthesis resources and post-P&R Fmax, and express speedups normalized to 100 MHz. These results show that even a modest FPGA can outperform our CPU state-vector baseline on small-n kernels while preserving deterministic, cycle-accurate timing for small-to-medium quantum workloads through spatial parallelism and hardware-level determinism.
This paper addresses the question of understanding quantum algorithms in terms of unitary operators. Many quantum algorithms can be expressed as applications of operators formed by conjugating so-called classical operators. The operators that are used for conjugation are determined by the problem and any additional structure possessed by the Hilbert space that is acted upon. We prove many commutative laws for these different operators, and we use those to phrase and analyze old and new problems and algorithms. As an example, we review the Abelian subgroup problem. We then introduce the problem of determining a group homomorphism, and we give classical and quantum algorithms for it. We also generalize Deutsch's problem and improve the previous best algorithms for earlier generalizations of it.
Processing quantum information using quantum three-level systems or qutrits as the fundamental unit is an alternative to contemporary qubit-based architectures with the potential to provide significant computational advantages. We demonstrate a fully programmable two-qutrit quantum processor by utilizing the third energy eigenstates of two transmons. We develop a parametric coupler to achieve excellent connectivity in the nine-dimensional Hilbert space enabling efficient implementations of two-qutrit gates. We characterize our processor by realizing several algorithms like Deutsch-Jozsa, Bernstein-Vazirani, and Grover's search. Our hardware-efficient protocols allow us to show that two stages of Grover's amplification can improve the success rates of an unstructured search with quantum advantage. Our results pave the way for building fully programmable ternary quantum processors using transmons as building blocks for a universal quantum computer.