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/

Zendy Pro

Presents the zaia usage as premium feature

ZAIA

Presents AI Discovery search usage as a premium feature

AI Discovery

Presents AI Discovery explain and summary usage as a premium feature

Content Analysis

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Presents the pdf analysis as premium feature

PDF Analysis

1500 Top-up

3000 Top-up

Zendy Basic

2500 Top-up

Zendy Unlimited

Presents the access of premium content as premium feature

Premium Content

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?