Sample complexity of hidden subgroup problem

DOI10.1016/j.tcs.2022.04.014OpenAlexW3181646273MaRDI QIDQ2672576

Zekun Ye, Lvzhou Li

Publication date: 13 June 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2107.02987

zbMATH Keywords

quantum computingfinite groupsample complexityhidden subgroup problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The query complexity of order-finding
• Quantum mechanical algorithms for the nonabelian hidden subgroup problem
• Optimal separation in exact query complexities for Simon's problem
• Learning functions of \(k\) relevant variables
• The true sample complexity of active learning
• Query complexity of generalized Simon's problem
• The quantum query complexity of the hidden subgroup problem is polynomial
• Quantum algorithms for learning and testing juntas
• The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
• Hidden translation and orbit coset in quantum computing
• Fast quantum algorithms for computing the unit group and class group of a number field
• Polynomial time quantum algorithm for the computation of the unit group of a number field
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Quantum algorithms and the Fourier transform
• Learning DNF over the Uniform Distribution Using a Quantum Example Oracle
• Quantum Computation and Lattice Problems
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• The List-Decoding Size of Fourier-Sparse Boolean Functions
• Theory of Disagreement-Based Active Learning
• A quantum algorithm for computing the unit group of an arbitrary degree number field
• Hidden Symmetry Subgroup Problems
• EFFICIENT QUANTUM ALGORITHMS FOR SOME INSTANCES OF THE NON-ABELIAN HIDDEN SUBGROUP PROBLEM
• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• Automata, Languages and Programming
• Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
• Quantum computing