Random measurement bases, quantum state distinction and applications to the hidden subgroup problem

DOI10.1007/S00453-008-9231-XzbMATH Open1169.81011arXivquant-ph/0512085OpenAlexW2013011515MaRDI QIDQ835652FDOQ835652

Pranab Sen, Martin Roetteler, Jaikumar Radhakrishnan

Publication date: 31 August 2009

Published in: Algorithmica (Search for Journal in Brave)

Abstract: We show that measuring any two quantum states by a random POVM, under a suitable definition of randomness, gives probability distributions having total variation distance at least a universal constant times the Frobenius distance between the two states, with high probability. This result gives us the first sufficient condition and an information-theoretic solution for the following quantum state distinction problem: given an a priori known ensemble of quantum states, is there a single POVM that gives reasonably large total variation distance between every pair of states from the ensemble? Our random POVM method also gives us the first information-theoretic upper bound on the number of copies required to solve the quantum state identification problem for general ensembles, i.e., given some number of independent copies of a quantum state from an a priori known ensemble, identify the state. The standard quantum approach to solving the hidden subgroup problem (HSP) is a special case of the state identification problem where the ensemble consists of so-called coset states of candidate hidden subgroups. Combining Fourier sampling with our random POVM result gives us single register algorithms using polynomially many copies of the coset state that identify hidden subgroups having polynomially bounded rank in every representation of the ambient group. These HSP algorithms complement earlier results about the powerlessness of random Fourier sampling when the ranks are exponentially large, which happens for example in the HSP over the symmetric group. The drawback of random Fourier sampling based algorithms is that they are not efficient because measuring in a random basis is not. This leads us to the open question of efficiently implementable pseudo-random measurement bases.

Full work available at URL: https://arxiv.org/abs/quant-ph/0512085

zbMATH Keywords

quantum algorithmshidden subgroup problemquantum Fourier transformsFrobenius distanceGel'fand pairsensemble quantum state distinctionrandom orthonormal measurement bases

Mathematics Subject Classification ID

Quantum computation (81P68)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Reversing quantum dynamics with near-optimal quantum and classical fidelity
• The Symmetric Group Defies Strong Fourier Sampling
• A ‘Pretty Good’ Measurement for Distinguishing Quantum States
• Numerical Cubature Using Error-Correcting Codes
• STACS 2005
• Refinement of the upper bound of the constant in the central limit theorem
• Quantum mechanical algorithms for the nonabelian hidden subgroup problem
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• On quantum algorithms for noncommutative hidden subgroups
• Learning mixtures of arbitrary gaussians
• Optimal measurements for the dihedral hidden subgroup problem
• Automata, Languages and Programming

Cited In (7)

• Identification of quantum hashes: numerical experiment
• Two-sided bounds on minimum-error quantum measurement, on the reversibility of quantum dynamics, and on maximum overlap using directional iterates
• The independence of reduced subgroup-state
• Generating a statet-design by diagonal quantum circuits
• Commuting quantum circuits and complexity of Ising partition functions
• Random positive operator valued measures
• Quantum algorithms for algebraic problems

This page was built for publication: Random measurement bases, quantum state distinction and applications to the hidden subgroup problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q835652)