The Optimal Single Copy Measurement for the Hidden Subgroup Problem

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.

8 pages. Error in main proof fixed

References in corpus (9)

• Reversing quantum dynamics with near-optimal quantum and classical fidelity
• Efficient Quantum Circuits for Schur and Clebsch-Gordan Transforms
• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• Efficient Quantum Transforms
• A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
• The Hidden Subgroup Problem - Review and Open Problems
• Hidden Subgroup States are Almost Orthogonal
• How many copies are needed for state discrimination?
• How a Clebsch-Gordan Transform Helps to Solve the Heisenberg Hidden Subgroup Problem

Cited by in corpus (6)

• Two-sided bounds on minimum-error quantum measurement, on the reversibility of quantum dynamics, and on the maximum overlap problem using directional iterates
• Two-sided estimates of minimum-error distinguishability of mixed quantum states via generalized Holevo-Curlander bounds
• Error rates of Belavkin weighted quantum measurements and a converse to Holevo's asymptotic optimality theorem
• Using post-measurement information in state discrimination
• Estimates of non-optimality of quantum measurements and a simple iterative method for computing optimal measurements
• An Improved Query for the Hidden Subgroup Problem