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

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-1}^m$ to $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, wherein 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.

7 pages, 1 figure

References in corpus (18)

• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum Algorithms Revisited
• Programmable quantum gate arrays
• Quantum factoring, discrete logarithms and the hidden subgroup problem
• Quantum learning and universal quantum matching machine
• A universal programmable quantum state discriminator that is optimal for unambiguously distinguishing between unknown states
• Storing quantum dynamics in quantum states: stochastic programmable gate for U(1) operations
• Quantum multimeters: A programmable state discriminator
• Probabilistic implementation of universal quantum processors
• Quantum Template Matching
• Universal measurement apparatus controlled by quantum software
• Quantum pure-state identification
• Unambiguous pure state identification without classical knowledge
• Efficient universal programmable quantum measurements
• Approximate programmable quantum processors
• Probabilistic quantum multimeters
• Improving performance of probabilistic programmable quantum processors
• Experimental realization of a programmable quantum-state discriminator and a phase-covariant quantum multimeter

Cited by in corpus (1)

• Quantum Machines