The Optimal Single Copy Measurement for the Hidden Subgroup Problem
Authors:
Preprint
Abstract
The optimization of measurements for the state distinction problem has recently been applied to the theory of quantum algorithms with considerable successes, including efficient new quantum algorithms for the non-abelian hidden subgroup problem. Previous work has identified the optimal single copy measurement for the hidden subgroup problem over abelian groups as well as for the non-abelian problem in the setting where the subgroups are restricted to be all conjugate to each other. Here we describe the optimal single copy measurement for the hidden subgroup problem when all of the subgroups of the group are given with equal a priori probability. The optimal measurement is seen to be a hybrid of the two previously discovered single copy optimal measurements for the hidden subgroup problem.Keywords
All Related Versions
- Version 1, 2007-06-29, ArXiv
- Version 2, 2008-01-22, ArXiv
- Published version: Physical Review A, 77 (3).
This publication has 8 references indexed in Scilit:
- For distinguishing conjugate Hidden subgroups, the pretty good measurement is as good as it getsQuantum Information & Computation, 2007
- Efficient Quantum Circuits for Schur and Clebsch-Gordan TransformsPhysical Review Letters, 2006
- A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup ProblemSIAM Journal on Computing, 2005
- Quantum solution to the hidden subgroup problem for Poly-Near-Hamiltonian groupsQuantum Information & Computation, 2004
- Reversing quantum dynamics with near-optimal quantum and classical fidelityJournal of Mathematical Physics, 2002
- On Quantum Algorithms for Noncommutative Hidden SubgroupsAdvances in Applied Mathematics, 2000
- A ‘Pretty Good’ Measurement for Distinguishing Quantum StatesJournal of Modern Optics, 1994
- Optimum testing of multiple hypotheses in quantum detection theoryIEEE Transactions on Information Theory, 1975