Singlet
← All research questions
Q30 / Preparation & verification / question

What limits STP preparation of accepted quantum witnesses?

Bound the STP cost of preparing a state close to an accepted witness, with explicit trace-distance error and success probability.

Discuss this question
Working mathematical formulation

Fix a uniform family of STP verifiers VxV_x, a witness encoding, a polynomial register bound, and a completeness/soundness gap. For YES instances let AxA_x be the set of states accepted above the completeness threshold. What is the minimum expected STP preparation cost, from mixed inputs with declared ancillas, of preparing a state within trace distance ε\varepsilon of some member of AxA_x, conditioned on a specified set of measurement outcomes with total probability at least pp? Can subsystem-spin or multiplicity structure bound this cost while keeping verification polynomial?

Scope & assumptions

An unrelativized lower bound separating efficient preparation from all quantum algorithms can depend on unresolved complexity assumptions. State such assumptions, or prove a restricted-model or oracle result. Easy preparation of singlets or coupling-tree states does not establish efficient preparation of arbitrary witnesses.

Why this is interesting

The distinction is between states useful for BQP\mathsf{BQP} computation and QMA\mathsf{QMA} witnesses. Testing local spin structure need not give a method to prepare an accepted global state.

A place to start

Begin with the randomized-edge verifier in Q15. Separate preparation of any accepted witness from preparation of one prescribed ground state, then ask which spin data gives a lower bound or a constructive preparation procedure.

Related work

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

  1. The two-qubit singlet/triplet measurement is universal for quantum computing given only maximally-mixed initial states ↗

    Terry Rudolph, Shashank Soyuz Virmani · 2023

    Read the relevance note
  2. Complexity classification of local Hamiltonian problems ↗

    Toby Cubitt, Ashley Montanaro · 2016

    Read the relevance note

Related questions

Q15 / QuestionWhat is the STP cost of preparing a Quantum Max-Cut witness?Compare verification by a weighted random-edge singlet test with STP preparation of a state whose Quantum Max-Cut objective is near optimal.Q16 / QuestionHow are product tests expressed in subsystem spin?Express the product test as triplet projections on corresponding pairs from two unentangled registers. Analyze completeness and soundness when it is used in a two-witness verification protocol.

Discuss this question

Continue on GitHub Propose a research question

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