⚛️ quantum physics

Permutation tests for quantum state identity

This paper establishes the optimal measurement for the quantum state identity problem in the general two-sided error regime via semidefinite programming and representation theory, while also proposing a general subgroup-based test and an efficient approximation using classical permutations and Swap tests.

Original authors: Harry Buhrman, Dmitry Grinko, Philip Verduyn Lunel, Jordi Weggemans

Published 2026-04-15

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Harry Buhrman, Dmitry Grinko, Philip Verduyn Lunel, Jordi Weggemans

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective in a high-tech lab. Your job is to solve a mystery involving a stack of quantum cards. You are given $n$ cards, and you know a very specific rule about them: either all the cards are identical copies of each other, OR they are all completely different from one another.

Your goal is to look at the stack and shout, "They're all the same!" or "They're different!" with as much certainty as possible.

This is the Quantum State Identity Problem. For decades, scientists knew the "perfect" way to solve this, but it was like trying to solve a puzzle by checking every single possible arrangement of the cards at once—a task so huge it would take a supercomputer forever.

This paper, written by a team of quantum researchers, does three main things:

It proves that the "perfect" (but slow) method is actually the best possible method, even if you relax the rules slightly.
It creates a new, flexible toolkit to test groups of cards using smaller, faster sub-groups.
It invents a clever, fast "tree-like" strategy that gets almost as good results as the perfect method, but is much easier to build in a real lab.

Here is a breakdown of their findings using everyday analogies.

1. The "Perfect" but Slow Method: The Permutation Test

Imagine you have a deck of cards and you want to know if they are all the same.

The Old Way (Swap Test): If you only have two cards, you can just swap them. If they are identical, the swap does nothing special. If they are different, the swap creates a "glitch" you can detect. This is called the Swap Test.
The "Perfect" Way (Permutation Test): If you have 100 cards, the perfect method involves shuffling them in every possible order (there are $100!$ ways to do this—more than the number of atoms in the universe!) and checking if the result looks the same.

The Problem: This "Perfect" method is mathematically unbeatable, but it's impossible to build a machine that shuffles cards in $100!$ different ways. It's too complex.

The Paper's First Discovery:
For a long time, scientists wondered: "If we stop demanding that our test be 100% perfect in every scenario (allowing for a tiny bit of error), can we find a simpler, faster way that works just as well?"

The authors say No. Even if you relax the rules, the "Perfect" method (Permutation Test) is still the champion. No matter how you slice it, you can't beat its accuracy. However, since building the "Perfect" machine is too hard, we need a "good enough" shortcut.

2. The Flexible Toolkit: The "G-Test"

Since the "Perfect" method is too heavy, the authors propose a middle ground. Imagine you don't need to check every possible shuffle of the cards. What if you only check shuffles within a specific club or subgroup?

They call this the G-Test.

The Circle Test: Imagine the cards are arranged in a circle. You only check if shifting everyone one seat to the left changes anything. This is fast and works great if the number of cards is a prime number (like 7 or 11).
The General G-Test: You can pick any subgroup of shuffles you like. The paper provides a mathematical formula (using something called "Kostka numbers," which are like secret codes for how groups fit together) to tell you exactly how good your chosen subgroup will be.

The Analogy: Instead of checking every possible way to rearrange a room's furniture, you only check if the furniture fits in a specific pattern (like a circle or a square). It's not as thorough as checking everything, but it's much faster, and you can calculate exactly how likely you are to miss a mistake.

3. The New Hero: The "Iterated Swap Tree" (IST)

This is the paper's most practical invention. They wanted a method that is:

Fast: Uses only simple "Swap Tests" (comparing two cards at a time).
Scalable: Works for any number of cards (specifically powers of 2, like 8, 16, 32).
Accurate: Almost as good as the impossible "Perfect" method.

How it works (The Tournament Bracket):
Imagine a tennis tournament.

You have 8 players (quantum states).
First, you pair them up randomly and have them play a match (a Swap Test).
If a match detects a difference, you stop and say, "They are different!"
If the match says "Same," the winners move to the next round.
You repeat this, pairing the winners, until you have one champion left.

This structure looks like a tree (hence "Iterated Swap Tree").

Why it's clever: It uses a random shuffle at the start so that the "bad" cards (the ones that are different) are scattered randomly. Then, the tree structure ensures that if there is any difference, it has a very high chance of being caught in one of the matches.
The Result: The authors proved that for large numbers of cards, this simple "Tournament" method is almost as good as the impossible "Perfect" method. It catches errors with nearly the same probability but uses a machine that is exponentially easier to build.

Summary of the "Big Picture"

The Problem: We need to know if a bunch of quantum states are identical or different.
The Truth: The mathematically perfect way to do this is too complex to build.
The Solution:
1. We proved you can't do better than the perfect method, even if you try to cheat.
2. We created a formula to test any "sub-group" of shuffles.
3. We built a Tournament Bracket (Iterated Swap Tree) that uses simple, pairwise comparisons to get results that are practically perfect for real-world quantum computers.

In a nutshell: The authors took a problem that required checking "every possible universe" and found a way to solve it by running a simple, randomized "tournament" that catches the cheaters almost every time, using equipment we can actually build today.

1. Problem Definition: Quantum State Identity (QSI)

The paper addresses the Quantum State Identity (QSI) problem, a fundamental task in quantum information where one must decide whether $n$ unknown quantum states $|\psi_1\rangle, \dots, |\psi_n\rangle$ are all identical or if at least one is different.

Promise: The input states satisfy a strict promise: they are either all identical, or they are pairwise orthogonal (or a mix where some are identical and others orthogonal).
Input: $n$ states of local dimension $d$ .
Goal: Distinguish between the "Equal" case (all states identical) and the "Unequal" case (at least one pair is orthogonal) with high probability.
Error Regimes:
- One-sided error: The algorithm must be perfect on the "Equal" case (perfect completeness) and minimize error on the "Unequal" case (soundness).
- Two-sided error: The algorithm aims to maximize the average success probability given a prior probability $p$ that the states are equal.

Context: For $n=2$ , the Swap Test is the optimal solution under one-sided error. For arbitrary $n$ , the Permutation Test (applying a superposition of all permutations in $S_n$ ) was known to be optimal under one-sided error. However, its optimality in the general two-sided error regime was an open question. Furthermore, the Permutation Test has high circuit complexity (requiring an ancilla of dimension $n!$ and a Fourier transform over $S_n$ ), prompting the search for simpler, near-optimal alternatives like the Circle Test (using cyclic group $C_n$ ).

2. Methodology

The authors employ a combination of Semidefinite Programming (SDP) and Representation Theory to analyze the problem structure.

SDP Formulation: They formulate the optimal measurement problem as an SDP to maximize the success probability. The primal problem seeks the optimal Positive Operator-Valued Measure (POVM) to distinguish between the density matrices of the "Equal" and "Unequal" cases.
Haar Randomness & Minimax: To handle the fact that the basis of the states is unknown, they assume the states are acted upon by a Haar-random unitary. Using the Minimax Theorem and symmetry arguments, they prove that this assumption is without loss of generality; the optimal strategy for an adversarial unknown basis is equivalent to the strategy for a Haar-random basis.
Representation Theory: They utilize Schur-Weyl duality to decompose the tensor product space $(\mathbb{C}^d)^{\otimes n}$ $(C^{d})^{\otimes n}$ into irreducible representations (irreps) of the symmetric group $S_n$ $S_{n}$ and the unitary group $U(d)$ $U (d)$ . Key tools include:
- Isotypic Projectors ( $\Pi_\lambda$ ): Projectors onto specific irreps $\lambda$ .
- Kostka Numbers ( $K_{\lambda, \mu}$ ): Combinatorial numbers relating partitions of $n$ to the multiplicities of irreps.
- Weingarten Calculus: Used to integrate over the unitary group to derive explicit forms of the density matrices.

3. Key Contributions and Results

A. Optimality of the Permutation Test (General Regime)

The paper resolves a 15-year-old open question by proving that the Permutation Test is optimal for all formulations of the QSI problem, even when the one-sided error requirement is relaxed.

Theorem 1 & 5: For any partition $\mu$ of $n$ (describing the distribution of identical vs. orthogonal states) and any prior probability $p$ , the Permutation Test (projecting onto the symmetric subspace) is the optimal measurement.
Threshold Prior ( $p^*$ ): The authors derive a critical threshold $p^*(\mu) = \frac{1}{1 + \binom{n}{\mu}}$ $p^{*} (μ) = \frac{1}{1 + ( μ n )}$ .
- If $p \ge p^*(\mu)$ , the optimal strategy is the Permutation Test (perfect completeness, soundness $1 - 1/\binom{n}{\mu}$ ).
- If $p < p^*(\mu)$ , the optimal strategy is the trivial test (always output "not equal").
Implication: Relaxing the one-sided error constraint does not improve the average success probability beyond what the Permutation Test achieves. Knowing the specific location of the differing states (the "ordered" case) also does not improve the success probability over the "unordered" case.

B. The General G-Test

The authors generalize the Permutation Test to any subgroup $G \subseteq S_n$ , termed the G-Test.

Mechanism: The test applies a superposition of permutations from subgroup $G$ (controlled by an ancilla) and measures the ancilla.
Performance Formula (Theorem 2): They derive an exact analytic expression for the soundness probability of any G-Test:
$P_s^G(\mu) = 1 - \frac{1}{\binom{n}{\mu}} \sum_{\lambda \vdash_d n} K_{\lambda, \mu} r_\lambda^G$
where $r_\lambda^G$ is the multiplicity of the trivial irrep of $G$ within the irrep $\lambda$ of $S_n$ .
Applications: This formula allows for the analysis of specific tests like the Circle Test ( $G=C_n$ ) and the Iterated Wreath Test.

C. The Iterated Swap Tree (IST)

To address the high circuit complexity of the Permutation Test ( $O(n!)$ ), the authors propose a new protocol called the Iterated Swap Tree (IST).

Structure: The IST applies $n-1$ Swap tests in a binary tree structure, preceded by a random classical permutation of the input labels. It corresponds to the G-Test where $G$ is an iterated wreath product of $S_2$ .
Performance Analysis:
- The authors introduce a combinatorial concept called "clicks" (potential detection events where a Swap test might reveal orthogonality).
- They derive a recursive upper bound on the soundness error using a function $\gamma(h, m)$ , where $n=2^m$ and $h$ is the number of distinct states.
- Theorem 3 & Corollary 3: For any fixed number of distinct states $h$ , as $n$ grows, the IST achieves soundness probability $\ge 1 - 1/n$ . This matches the asymptotic scaling of the optimal Permutation Test.
Significance: The IST achieves near-optimal performance using only $O(n)$ Swap tests and a single qubit for the final measurement, offering an exponential reduction in circuit complexity compared to the full Permutation Test.

4. Significance and Impact

Resolution of Open Problems: The paper definitively settles the optimality of the Permutation Test for the QSI problem in the general two-sided error setting, confirming that no other measurement can outperform it.
Theoretical Framework: It provides a unified mathematical framework (using SDP and Representation Theory) to analyze quantum state comparison problems, linking them to Kostka numbers and group representation multiplicities.
Practical Efficiency: By introducing the Iterated Swap Tree, the authors demonstrate that near-optimal performance can be achieved with significantly lower experimental overhead (linear number of gates vs. factorial). This is crucial for near-term quantum devices where implementing complex Fourier transforms over $S_n$ is infeasible.
Hypothesis Testing Geometry: The authors characterize the complete achievable region of Type I and Type II errors (completeness and soundness) as a parallelogram, providing a full trade-off curve for the problem.

In summary, this work bridges the gap between information-theoretic optimality and practical implementability in quantum state comparison, proving that while the Permutation Test is theoretically supreme, simpler tree-based protocols can approximate this optimality with feasible resources.