English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We study the hardness of the dihedral hidden subgroup problem. It is knownthat lattice problems reduce to it, and that it reduces to random subset sumwith density $> 1$ and also to quantum sampling subset sum solutions. Weexamine a decision version of the problem where the question asks whether thehidden subgroup is trivial or order two. The decision problem essentially asksif a given vector is in the span of all coset states. We approach this by firstcomputing an explicit basis for the coset space and the perpendicular space. Wethen look at the consequences of having efficient unitaries that use thisbasis. We show that if a unitary maps the basis to the standard basis in anyway, then that unitary can be used to solve random subset sum with constantdensity $>1$. We also show that if a unitary can exactly decide membership inthe coset subspace, then the collision problem for subset sum can be solved fordensity $>1$ but approaching $1$ as the problem size increases. Thisstrengthens the previous hardness result that implementing the optimal POVM ina specific way is as hard as quantum sampling subset sum solutions.

How hard is deciding trivial versus nontrivial in the dihedral coset problem?