Singlet
← All research questions
Q01 / Algorithms & primitives / direction

Which algorithmic primitives does subsystem spin suggest?

Can filtering, recoupling, or state comparison give an STP algorithm for a specified task? Identify its interference mechanism and compare its resource cost with a circuit implementation.

Discuss this question
Working mathematical formulation

Identify an explicit family of computational tasks and an STP protocol whose useful invariant, interference mechanism, or cost advantage has a direct subsystem-spin explanation. Specify the input encoding, access model, success probability, and asymptotic resources; compare against the best relevant gate-model and classical baselines.

Scope & assumptions

STP measurements have constant-size gate-model realizations. A proposed asymptotic improvement must use a specified baseline or physical cost model; changing the description alone cannot beat an optimal unrestricted gate-model implementation.

Why this is interesting

A useful new primitive should generate algorithms and explanations, not only another universal language. Filtering, recoupling, state comparison, and transport of relational information are candidate ingredients.

Explicit variants

  1. Search and amplitude amplification

    Fix the usual marked-item oracle and its encoded implementation cost. Construct an STP description of the search rotation or amplitude-amplification step and account separately for oracle queries, projector measurements, and failed branches.

  2. Simon’s problem

    For f(x)=f(y)f(x)=f(y) exactly when x⊕yx\oplus y is 00 or a hidden nonzero string ss, specify coherent access to ff in the encoding. Identify which multiplicity-space operation produces the linear constraints on ss, and bound queries and measurement cost.

  3. Forrelation

    Fix a stated forrelation promise and the usual phase-oracle access to its Boolean functions. Identify the interference statistic represented by the STP protocol and preserve the promised acceptance gap and oracle-query model.

  4. Comparing formulations

    For each family, compare against a named compilation baseline using the same input and oracle access. Record physical qubits, measurement count, rounds, precision, and success probability. An explanatory simplification and an asymptotic improvement are different outcomes.

A place to start

Choose one small task—search, a Simon-type promise, or a forrelation-like correlation—and write down what a pairwise projector would have to accomplish.

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. Symmetry Protected Quantum Computation ↗

    Michael H. Freedman, Matthew B. Hastings, Modjtaba Shokrian Zini · 2021

    Read the relevance note
  3. Forrelation: A Problem That Optimally Separates Quantum from Classical Computing ↗

    Scott Aaronson, Andris Ambainis · 2018

    Read the relevance note
  4. A fast quantum mechanical algorithm for database search ↗

    Lov K. Grover · 1996

    Read the relevance note
  5. Quantum Amplitude Amplification and Estimation ↗

    Gilles Brassard, Peter Høyer, Michele Mosca, Alain Tapp · 2002

    Read the relevance note

Related questions

Q41 / QuestionWhat is an SU(2)\mathrm{SU}(2) analogue of Grover search?What should “unstructured search” mean when the available operations are subsystem-spin measurements? Is there a direct quadratic speedup over classical search, and what coherent or adaptive structure produces it?Q02 / QuestionHow can order finding be expressed through STP?Describe the encoding, modular arithmetic, and readout of an STP order-finding protocol. Identify how its multiplicity-space operations represent periodicity and interference.Q03 / QuestionHow efficiently can we compile into STP?How much of the cost of a universal STP construction is essential?

Discuss this question

Continue on GitHub Propose a research question

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