Quantum computation through subsystem spin

Algorithms and compilation

We want to understand what Shor’s algorithm is doing in terms of subsystem spin, and to find algorithms built directly from spin measurements. Could quantum walks be formulated on spin-coupling trees? Could small-subsystem projectors implement a useful operation with fewer resources than its usual circuit decomposition?

Universality gives a polynomial simulation; its overhead still matters. For a circuit with $G$ gates and error tolerance $\varepsilon$, how many qubits, pair measurements, and adaptive rounds does an STP implementation require? For a direct algorithm, specify the input, output, success probability, and classical processing as well. Preparation and retries belong in the cost.

Specific targets: unstructured search, order finding, and spectral filtering.

The SWAP test

The SWAP test measures the symmetry of two quantum systems under exchange. For independent inputs, its outcome probabilities determine their overlap.

Write $F$ for SWAP. Since $F^2=I$ and $F=F^\dagger$, its eigenvalues are ±1. The two projectors are $P_+=(I+F)/2$ and $P_-=(I-F)/2$. A symmetric state satisfies $F|\Psi\rangle=|\Psi\rangle$; an antisymmetric state satisfies $F|\Psi\rangle=-|\Psi\rangle$. On two qubits, these are exactly the triplet and singlet spaces.

For independent inputs $\rho\otimes\sigma$, the swap identity gives

For pure inputs, the overlap is $|\langle\psi|\phi\rangle|^2$. Identical pure states always give the symmetric outcome; orthogonal states give either outcome with probability ½. A symmetric outcome alone does not certify that the states were identical. With two independent copies of a mixed state, the same test estimates its purity. Quantum fingerprinting compares compact quantum encodings of classical strings this way. The example below shows the comparison primitive on two qubits; a full protocol also specifies the encodings and repetitions with fresh inputs. [20]

The circuit prepares an ancilla in $|0\rangle$, applies a Hadamard, a controlled SWAP, and another Hadamard. For a pure joint data state $|\Psi\rangle$, its final state before readout is

Measuring the ancilla projects the two data qubits onto the singlet or triplet space. Keep those qubits and they can participate in the next measurement: this is singlet–triplet projection (STP). [1]

This ideal implementation is quantum nondemolition (QND) for the pair’s spin: without intervening dynamics, a repeated measurement returns the same outcome. It also preserves coherence within each sector; repeatability alone would not guarantee that property.

Once the data are correlated, the independent-input overlap formula no longer applies. A singlet gives the antisymmetric outcome with certainty. A measurement on an overlapping pair can change the first pair’s subsequent outcome probabilities.

Representations and invariant subspaces

We find it useful to think of representation theory as a generalization of diagonalization. An eigenvector identifies a direction that a transformation preserves. For a whole group of transformations, we ask which subspaces are preserved by all of them.

A representation is a map $R:G\to U(V)$ preserving composition:

Here we use finite-dimensional complex unitary representations. For finite groups, or continuous representations of compact groups, choosing an invariant inner product lets us work in this setting.

A subspace $W\subseteq V$ is invariant if every matrix $R(g)$ maps the subspace into itself: $R(g)W\subseteq W$ for all $g\in G$. An irreducible representation, or irrep, has no proper nonzero invariant subspace. We can decompose the whole space into such pieces, using one basis change that makes every representation matrix block diagonal. Noncommuting matrices need not reduce all the way to one-dimensional blocks.

For an abelian group, the complex irreps are one-dimensional. Translations around a cycle are a familiar example: the Fourier modes are common eigenvectors, and translating multiplies each mode by a phase. In this sense, irrep types generalize frequencies.

Multiplicity and the commutant

Take $\mathbb Z_2=\{e,s\}$, with $s^2=e$, and let it act on $V=\mathbb C^3$. A representation assigns a matrix to each of the two group elements. Here those $3\times3$ matrices are

The identity acts as $I_3$, and $R(s)^2=R(e)$, as required by the group multiplication. The one-dimensional sign representation occurs twice: $s$ acts by −1 on each of the first two coordinate lines. The third coordinate carries the trivial representation, with both elements acting by +1.

The two-dimensional minus-sign eigenspace is determined by the representation, but its decomposition into two invariant lines is not unique. Any orthonormal basis of that plane gives two equivalent copies of the sign representation.

We separate the type of irrep from how many copies occur:

The direct sum $\bigoplus$ collects distinct irrep types. The tensor product $\otimes$ records copies of one type: $\dim M_\lambda$ is its multiplicity. Dimensions add across the sum and multiply within a term. The full block containing one type is called its isotypic component; it is canonical even when a basis of the multiplicity space is not.

What can an operator do while commuting with every $R(g)$? Schur’s lemma says it can act on the multiplicity space while leaving the irreducible factor alone:

These operators form the commutant of the representation. They can mix equivalent copies of an irrep, but cannot mix inequivalent irrep types. [21]

Schur–Weyl duality

Start with representations of two groups on the same vector space. For $n$ qubits, that space is the whole Hilbert space

The groups are $\mathrm{SU}(2)$, acting by the same rotation on every qubit, and $S_n$, acting by permutations of the qubits. Both representations assign operators on $\mathcal H_n$:

These are two families of $2^n\times2^n$ matrices acting on the same state. For every rotation $U$ and permutation $\pi$, their actions commute:

Applying the same rotation to every tensor factor and then reordering the factors gives the same result as doing those operations in the opposite order. The commutation is between the two group actions; two rotations need not commute with each other, nor need two permutations.

Commuting representations on a shared space are the starting point. Schur–Weyl duality makes the stronger statement that their generated operator algebras are mutual commutants. Every linear operator commuting with all collective rotations is a complex linear combination of qubit permutations. Conversely, every linear operator commuting with all qubit permutations is a complex linear combination of collective rotations. [21]

Consequently, a single change of basis decomposes this same Hilbert space into paired irreducible representations of the two groups:

Collective rotations act on the spin-$J$ factor $V_J$, of dimension $2J+1$, and leave $M_J$ alone. Permutations act irreducibly on $M_J$ and leave $V_J$ alone. Each pair $V_J\otimes M_J$ occurs once in the joint decomposition. If we look only at rotations, $\dim M_J$ counts the copies of spin $J$; if we look only at permutations, $2J+1$ counts the copies of the corresponding permutation irrep. These are two descriptions of the same block of states. [21]

Three qubits: two copies of spin ½

The first pair can have spin zero or spin one. Adding a third spin-½ gives spin ½ from the first case, and either spin ½ or spin 3/2 from the second. Thus

A measurement of total spin alone cannot distinguish the two spin-½ copies. They transform identically under collective rotations but have different pairwise correlations. Exchanging the second and third qubits can mix the copies. Changing which pair we couple first changes the multiplicity basis.

Young diagrams keep track of the same structure. For qubits, the row lengths are $(n/2+J,n/2-J)$. At three qubits, shape $(2,1)$ has two standard tableaux and corresponds to spin ½; shape $(3)$ has one and corresponds to spin 3/2. The number of tableaux counts coupling paths. The difference between row lengths is $2J$.

The Schur transform coherently changes from individual-qubit coordinates to the labels $|J,m,\alpha\rangle$: total spin, a spin basis index, and a multiplicity basis index. Efficient quantum circuits for this transform are known. Measuring only $J$ projects onto a whole sector; it is a different operation from performing the full coherent transform. [14]

Every pair projector commutes with collective rotations, so it has the form

STP acts on the multiplicity factor within each total-spin sector. Starting from mixed input, the spin factor remains maximally mixed: no external spatial reference frame is required. The earlier Rudolph–Virmani construction supplied suitably chosen single-qubit states; their later theorem removes that input requirement. [36][1][28]

Antisymmetry as a resource?

Is the resource antisymmetry itself, or the information encoded in how antisymmetry is distributed? These are different proposals. For fixed global spin, the sum of all pairwise singlet probabilities is fixed, but their distribution can change. States can also differ in multiplicity-space coherence that this sum does not record. A candidate resource should distinguish states according to a specified computational task, rather than simply count singlet weight.

The fully symmetric sector provides a useful comparison: every internal pair is triplet, so internal STP leaves its state unchanged. Extra qubits can change the available operations. A resource theory needs a task, a set of free states, and a restricted set of free operations. Calling the full universal STP model free would make many interesting states cheap by definition. We have to say which restriction makes the proposed resource costly. Q10 / Research directionCan antisymmetry become an operational resource?↗Treat measurements within fixed blocks as free and charge for measurements between blocks. Can an average monotone of singlet correlations or multiplicity information bound state-conversion cost?

States within a spin sector

STP preserves global spin sector: its projectors commute with collective rotations. Conditioning can change the weights assigned to different sectors of a mixed input, while transforming the state inside their multiplicity spaces. It does not freely create coherence between distinct global-spin sectors.

For maximally mixed input, sector J has probability (2J + 1) dim M_J / 2ⁿ; typical total spin grows on the order of √n, rather than being concentrated at zero. The interesting question is what conditional protocols can organize inside these sectors.

Even within J = 0, there is more than one state. Here the total amount of pairwise singlet weight is fixed. Change a relative phase and watch that same total redistribute.

What do successive measurements build?

We start with no correlations: each qubit has state $I/2$. For two qubits, a singlet–triplet measurement has the following branches:

The singlet branch is a pure entangled state. The triplet branch is still mixed: it is uniform on a three-dimensional subspace. A second test of the same pair returns triplet with certainty and leaves that state unchanged. Learning the spin label does not select a pure state within the corresponding space.

In fact, this mixed triplet is separable. Choose a pure qubit state uniformly over directions, prepare two copies, then forget the direction. Averaging those product states gives exactly $P_t/3$. The triplet space contains entangled states, but the particular state prepared from mixed input has no entanglement. If we forget the measurement outcome as well, the two branches average back to $I/4$.

Symmetric blocks and overlapping measurements

The same construction works for a larger block of $k$ qubits:

The measure is normalized and uniform over pure qubit states. The integral is supported on the symmetric spin-$k/2$ irrep and is invariant under collective rotations; these facts and trace one determine the normalized projector. It is a mixture of product states, even though being fully symmetric does not by itself imply separability.

Every internal pair in this block is triplet. To change it using STP, we need to interact it with something outside the block. Preparing two symmetric blocks independently does not make their union fully symmetric. An overlapping measurement can change their internal correlations and entangle systems across the old block boundaries.

Prepare simple blocks independently, then measure a pair that crosses their boundaries. Starting with two singlets, either outcome on a cross-pair gives a useful state: new singlet pairs, or two spin-one pairs entangled into total spin zero. Starting with two mixed triplets can also create entanglement. The output need not remain a collection of the original blocks.

Overlapping singlet constraints

Disjoint pairs can each be singlets, but two pairs sharing a qubit cannot both be perfect singlets. For three qubits,

If 1–2 is a singlet, measuring 2–3 gives singlet with probability ¼. Retaining that outcome creates a singlet on 2–3, but 1–2 is no longer certainly singlet. The constraints are incompatible as simultaneous certainties; the sequence of outcomes is possible.

Triplet constraints have a common solution: every pair in a fully symmetric state is triplet. On a connected graph, the common triplet subspace is exactly the fully symmetric subspace. Overlapping triplet projectors still do not commute, so a later measurement can disturb an earlier triplet outcome. A promise of lower global spin excludes the fully symmetric solution.

Could the cost of redistributing antisymmetric correlations help explain computational hardness? In Quantum Max-Cut, we optimize singlet weight on incompatible overlapping edges. In an STP computation, we can follow the singlet correlation between an untouched reference and an output qubit. We want to understand which properties of the intermediate states control the cost of producing the desired correlations. Frustration alone does not answer that question.

The state contains more information than its spin weights

Starting from mixed input, every conditional state produced by STP remains invariant under collective rotations. In Schur coordinates it therefore has the form

The orientation factor stays maximally mixed. The probabilities $p_J$ describe how much weight is in each global-spin sector, while $\sigma_J$ describes the state in its multiplicity space. A pair measurement acts within these sectors. Conditioning reweights them and changes their multiplicity states; it does not transfer an amplitude from one global $J$ to another. Averaging over all outcomes conserves the sector weights of a closed register.

This matters for preparation and compilation. Universality of the STP model does not mean that we can prepare every physical pure state from mixed qubits. The operations also preserve real density matrices in the computational basis. Universal computation is encoded in relational degrees of freedom, with the relevant input and readout conventions. The physical target, the encoding, and the permitted ancillary systems are part of a preparation problem.

For a particular recorded history $h$, let $K_h$ be the ordered product of its pair projectors. From mixed input on $n$ qubits,

Projectors on overlapping pairs need not commute. Their product need not be a projector, so the state can acquire a nonuniform spectrum and correlations that are invisible in the most recently measured spin label. This is one reason we want to follow what we can create over time, rather than describe a computation only by its final answer.

Keeping a resource is different from starting again

A fresh mixed pair yields a singlet once every four attempts on average. We can keep that pair and prepare another independently. Two singlets then cost eight pair measurements on average in this simple procedure, with fresh mixed pairs available for retries. The particular four-qubit history in which both first attempts succeed has probability only $1/16$. A branch probability alone does not specify the cost of a protocol that can keep, retry, or recycle intermediate states.

Could a compiler work with these intermediate resources directly? It might keep track of symmetric blocks, singlets, multiplicity states, and which failed branches are still useful. We would then ask what a proposed conversion accomplishes, with what accuracy, and at what total cost. Entropy, purity, spin weights, and entanglement are useful diagnostics, but the figure gives no reason to identify any one of them with computational power.

Start from a cut of the same graph

The EPR algorithm begins with a fully polarized state, which is easy to prepare. Why not try a similar approach on the hard side of the phase diagram, starting from a Max-Cut solution? Finding the cut may be NP-hard, but its bit string has an efficient description. Merlin could supply it; Arthur could prepare that product state and try to move from there.

The graph should stay the same. Write the Quantum Max-Cut energy as $Q_G=-\sum_{ij}w_{ij}P_s^{ij}$. A computational-basis state $|x\rangle$ has energy $\langle x|Q_G|x\rangle=-\tfrac12\operatorname{Cut}_G(x)$. A maximum cut therefore gives a best computational-basis starting state for this objective. It does not supply a quantum ground state.

Here is a concrete interpolation to try. Let $P_{t_0}$ project onto $(|01\rangle+|10\rangle)/\sqrt2$, one particular triplet, and put

At $t=0$, this is the classical Max-Cut Hamiltonian $-\sum_{ij}w_{ij}(I-Z_iZ_j)/2$. At $t=1$, its local levels are −2 for $t_0$, −1 for the singlet, and 0 for the other two triplets. This is twice the $s=1/2$ interaction in Figure 4, whose ground-energy problem is StoqMA-complete. [5]

This path is part of a direct interpolation from Quantum Max-Cut: hold the singlet coefficient fixed and lower the selected triplet from 0 to −2. The classical Max-Cut point lies halfway along that route. Starting there gives a classically described product state; starting at a Quantum Max-Cut ground state would require explaining how that state was prepared.

There is an immediate obstruction: this path preserves Hamming weight. A maximum cut can be in a different magnetization sector from the target ground state. A cut-aligned Z field can select a starting state, but cannot move it between these sectors. Perhaps the witness should instead specify a good cut in a useful sector. We then need a polynomial gap along the path, or another preparation argument giving enough low-energy overlap.

This is the point of the proposed containment $\mathrm{StoqMA}\subseteq\mathrm{QCMA}$: the space might be navigable from a good starting position, even if finding that position is hard. The claim needs a short useful guide for every YES instance. The verifier need not prove that the supplied cut is optimal; it must reach low energy when a good guide exists, and reject all guides on NO instances.

The Lee–Yang gap theorem proves this kind of quantum preparation bound for its stated interaction class and uniform field. It does not yet justify cut-aligned fields here. A classical Markov-chain version would separately need a mixing bound and efficiently computable transitions. These Hamiltonian paths also permit operations beyond bare STP: the selected triplet distinguishes a spatial axis. [16][17][18][19]

A broader question is: which spin-constraint problems have classical guides as witnesses, and which are QCMA-complete? That question remains useful independently of the proposed containment.

Beyond pairwise qubit measurements

The primitive can also be varied. A three- or four-qubit total-spin measurement resolves different subspaces from a sequence of pair tests. Even when the unrestricted computational power is the same, depth, adaptivity, and the retained state may differ.

For qudits, we can measure irreducible labels of SU(d). More generally, fix a representation of a compact group and ask what computation is generated by measuring the irrep of a small subsystem. Which representations and measurements support universality? Which restrictions admit efficient classical simulation?

What computation is possible in shallow depth?

If STP is our primitive, we want analogues of familiar circuit-depth questions: what can constant depth do, and what changes at logarithmic depth? We have to count the classical computation between measurements as well. An unrestricted classical controller could compute Majority itself.

A concrete benchmark is to encode each unknown input bit in a pair: 1 as a singlet, 0 as the mixed triplet sector. For an odd number of pairs, can a shallow STP protocol determine whether most pairs are singlets? One parallel measurement layer reads all the bits; logarithmic-depth classical aggregation gives a baseline. The question is whether quantum processing helps when the total classical-control depth is restricted, for example to AC⁰.

A second benchmark is intrinsically about spin: distinguish a state supported on low total-spin sectors from one supported on high total-spin sectors. Specify the separation between the sectors, the number of copies, and whether the state must be retained. Total spin is not the Hamming weight of a bit string, so this is a different threshold problem.

Related lower-bound methods

This is an existing family of ideas: symmetry-assisted adversaries, compressed permutation oracles, and group path recording. Recent work explicitly connects compressed-oracle arguments to multiplicative adversaries. We would like to understand whether subsystem spin suggests a useful formulation or application. [9][15][10][11]

We should keep the full representation structure in view. Sector probabilities alone may forget exactly the multiplicity and coherence information that a sharp argument needs. And this mathematical purification trick is distinct from physically purifying noisy qubits.

Symmetric and antisymmetric subspaces also appear in a recent quantum-oracle separation between QMA(2) and QMA and in disentangler lower bounds. That is a connection worth pursuing, with the oracle model and dimension conventions intact. [8][13]