The hidden subgroup problem and MKTP

DOI10.1016/j.tcs.2019.06.012zbMath1434.68203OpenAlexW2954953566WikidataQ127566703 ScholiaQ127566703MaRDI QIDQ2330111

André L. Vignatti, Nicollas M. Sdroievski, Murilo V. G. da Silva

Publication date: 18 October 2019

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.06.012

zbMATH Keywords

hidden subgroup problemstatistical zero-knowledgetime-bounded Kolmogorov complexityNP-intermediate problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Subgroup theorems; subgroup growth (20E07) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Subgroups of symmetric groups (20B35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• SZK proofs for black-box group problems
• Solvable black-box group problems are low for PP
• Discrete logarithm and minimum circuit size
• Zero knowledge and circuit minimization
• Minimum Circuit Size, Graph Isomorphism, and Related Problems
• Circuit minimization problem
• The Knowledge Complexity of Interactive Proof Systems
• On the Structure of Polynomial Time Reducibility
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• ON THE COMPLEXITY OF THE HIDDEN SUBGROUP PROBLEM
• Polynomial-time theory of matrix groups
• Quantum Algorithms for a Set of Group Theoretic Problems
• Quantum Algorithms for Abelian Difference Sets and Applications to Dihedral Hidden Subgroups
• Power from Random Strings

This page was built for publication: The hidden subgroup problem and MKTP