Q22: Which spin problems are BQP-complete?

Working mathematical formulation

Define a promise problem on succinctly described spin networks, recoupling structures, or adaptive measurement histories and prove both $\mathsf{BQP}$ membership and $\mathsf{BQP}$ hardness under explicit reductions and precision conventions. Seek a natural formulation beyond simply relabeling a circuit. In the knot or tangle direction, seek a natural task beyond restating the standard Jones-polynomial approximation problem.

Why this is interesting

A useful complete problem can expose computational structure in another field. Braids, knots, and tangles are leads, not automatic evidence of hardness.

Explicit variants

Sampling formulations
Define a family of spin-native output distributions with an explicit classical instance description and approximation metric. Prove efficient quantum sampling and an appropriate sampling-hardness reduction; separately formulate any bounded-error decision problem extracted from those distributions. Specify the sampling complexity class and reduction rather than treating a sampling task as a language in $\mathsf{BQP}$ .

A place to start

Specify a small diagrammatic evaluation problem and decide whether it estimates an amplitude, a probability, or an adaptively generated distribution.

Related work

These works provide context and established results. They need not be the origin of this exact formulation.

Discuss this question

Continue on GitHub Propose a research question

Reading is public. Posting requires a GitHub account. You can also write to Kunal.