length $L$.

[No]{} Case:

:   $G$ has exactly one simple cycle $C^{(planted)}$ of length $L$, and no longer simple cycle.

Moreover, $C^{(planted)}$ can be efficiently found in polynomial time.

The proof of the above uses a simple extension of a relatively standard reduction (see e.g. @Vadhan02) from Hamiltonian Cycle. Starting with an instance $G_1$ of Hamiltonian Cycle, we replace each edge by a two-connected path of length $t$, for some integer $t$. For $L=nt$, this gives us $2^{L}$ cycles of length $L$ for every Hamiltonian cycle in $G_1$. Moreover, any simple cycle of length $L$ must correspond to a Hamiltonian Cycle in $G_1$. We add to $G$ a simple cycle of length $L$ on a separate set of $L$ vertices. This “planted” cycle is easy to find, since it forms its own connected component of size $L$. A full proof is deferred to Appendix \[app:count\_gap\_amplification\].

Armed with these, we form a function on the hypercube in $d = |E'|$ dimensions such that optimizing it is easy, but sampling is hard.

\[thm:cycle\_h\] There exists a function $h : {\mathbb{H}_{d}} \rightarrow [0, d]$ satisfying the following properties.

Efficiency:

:   $h$ can be computed efficiently on ${\mathbb{H}_{d}}$.

Easy Optimization:

:   One can efficiently 