Random measurement bases, quantum state distinction and applications to the hidden subgroup problem
From MaRDI portal
(Redirected from Publication:835652)
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.
Recommendations
- Automata, Languages and Programming
- For distinguishing conjugate hidden subgroups, the pretty good measurement is as good as it gets
- Weak Fourier-Schur Sampling, the Hidden Subgroup Problem, and the Quantum Collision Problem
- The power of basis selection in Fourier sampling: hidden subgroup problems in affine groups
- The hidden subgroup problem and permutation group theory
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 1775384 (Why is no real title available?)
- scientific article; zbMATH DE number 2174437 (Why is no real title available?)
- scientific article; zbMATH DE number 3349081 (Why is no real title available?)
- A ‘Pretty Good’ Measurement for Distinguishing Quantum States
- Automata, Languages and Programming
- For distinguishing conjugate hidden subgroups, the pretty good measurement is as good as it gets
- Learning mixtures of arbitrary Gaussians
- Numerical Cubature Using Error-Correcting Codes
- On quantum algorithms for noncommutative hidden subgroups
- Optimal measurements for the dihedral hidden subgroup problem
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum mechanical algorithms for the nonabelian hidden subgroup problem
- Refinement of the upper bound of the constant in the central limit theorem
- Reversing quantum dynamics with near-optimal quantum and classical fidelity
- STACS 2005
- The Hidden Subgroup Problem and Quantum Computation Using Group Representations
- The Symmetric Group Defies Strong Fourier Sampling
- The power of basis selection in Fourier sampling: hidden subgroup problems in affine groups
Cited in
(11)- Quantum algorithms for algebraic problems
- Generating a state t-design by diagonal quantum circuits
- Identification of quantum hashes: numerical experiment
- For distinguishing conjugate hidden subgroups, the pretty good measurement is as good as it gets
- On the distinguishability of random quantum states
- 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
- Weak Fourier-Schur Sampling, the Hidden Subgroup Problem, and the Quantum Collision Problem
- Automata, Languages and Programming
- Commuting quantum circuits and complexity of Ising partition functions
- Random positive operator valued measures
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)
