Algebraic and Graph-Property Tests for Quantum Functions

An exact commutativity test, graph colouring, and the missing robust algebra theorem

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

In the source model a finite-dimensional quantum function $F:X\to A$ assigns positive-semidefinite $d\times d$ measurement operators $M_{a\mid x}$ satisfying $\sum_{a\in A}M_{a\mid x}^2=I$ for each $x$. Sequential query probabilities are $d^{-1}\|M_{a_1\mid x_1}\cdots M_{a_q\mid x_q}\|_{\mathrm F}^2$, with the order interpreted as in the source. The function is commutative if all its measurement operators commute. A property is a class of such functions; a property tester seeks to distinguish membership from being far from the class using few queries. The algebra generated by the measurements is the smallest unital complex matrix algebra containing the operators and their adjoints. A test forces commutativity or an algebraic property when every perfectly passing strategy has that property under the test's specified equivalence.

Statement recorded in the supplied source.

Can one characterize when a test forces a quantum function to be commutative? What happens when graph properties are tested with quantum functions? Beyond dimension testing, can one design tests forcing the measurements of a quantum function to generate a specified algebra? Are there applications to algorithms, complexity theory, or cryptography? [S2]

Scope qualification.

This is a family of mathematical characterization and construction questions. Graph encodings, acceptance thresholds, robustness, distance, and equivalence of representations must be specified in individual results. The final application clause is a proposed direction, not a theorem claim.

Source status.

The supplied catalogue labels this record open. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-22.

Short English statement

Determine which tests constrain the algebra of a quantum function and how graph-property tests behave in that model.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004920 (OWR-8415359-008). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Complexity Theory $2022$, Oberwolfach Reports, DOI 10.4171/owr/2021/54, pp. 2955--3005 https://doi.org/10.4171/owr/2021/54.
• S3 Complexity Theory, Oberwolfach Reports 54/2021, primary report PDF https://ems.press/content/serial-article-files/46932. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

Can one characterize when a test forces a quantum function to be commutative? What happens when graph properties are tested with quantum functions? Beyond dimension testing, can one design tests forcing the measurements of a quantum function to generate a specified algebra? Are there applications to algorithms, complexity theory, or cryptography?

Scope of the attempted construction

The primary report, printed page 2974, asks several questions: characterizing tests forcing commutativity, testing graph properties, forcing specified algebras, and applications. We construct one exact three-query test in the literal positive measurement model. Its perfect-passing condition forces the stronger property of projective commutativity. It is therefore neither a characterization of all such tests nor a tester accepting every commuting positive-operator family. The distinction matters: commuting scalar fair-coin measurements are not projective and do not repeat their outcomes with certainty.

Two repetitions force projectivity

Take a finite input alphabet $X$ and finite output alphabet $A$, and positive operators $M_{a\mid x}$ with $\sum_aM_{a\mid x}^2=I$. Query $x$ twice and require the outputs to agree. Perfect passing means for every $a\ne b$ \[ 0=d^{-1}\|M_{a\mid x}M_{b\mid x}\|_{\rm F}^2. \] Thus the product is zero. Multiply the normalization by $M_{a\mid x}$ on the left; all other terms vanish and give $M_{a\mid x}^3=M_{a\mid x}$. Since this is a positive Hermitian matrix, each eigenvalue satisfies $t\ge0$ and $t^3=t$, hence is zero or one. The operators are therefore orthogonal projectors summing to the identity. Conversely a projective measurement repeats perfectly by orthogonality. Sampling every input with positive probability makes perfect passing enforce this conclusion for every input separately.

A three-query test forces exact pairwise commutativity

After establishing projectivity, write the projectors for two queries as $P_a,Q_b$. Query in the order $x,y,x$ and accept when the two outer outcomes agree. For $a\ne c$, the probability of outcomes $a,b,c$ is $d^{-1}\|P_aQ_bP_c\|_{\rm F}^2$. Perfect passing implies all such off-diagonal blocks vanish. Since $\sum_aP_a=I$, it follows that \[ Q_b=\sum_aP_aQ_bP_a, \] and hence $Q_b$ commutes with every $P_a$. Conversely, if the projectors commute, $P_aQ_bP_c=Q_bP_aP_c=0$ for $a\ne c$. Choose, with positive probability, a repeat test for each input and an outer-repeat test for each ordered input pair. Each branch uses at most three queries, and the combined tester passes with probability one exactly when all measurements are commuting projective measurements.

For already projective measurements the rejection probability for a fixed pair has the exact identity \[ \Pr\{a\ne c\} =\frac1{2d}\sum_{a,b}\|[P_a,Q_b]\|_{\rm F}^2. \] Indeed, for fixed $a,b$, the blocks $P_aQ_bP_c$, $c\ne a$, are orthogonal in the Frobenius inner product and sum to $P_aQ_b(I-P_a)$. The commutator is $P_aQ_b(I-P_a)-(I-P_a)Q_bP_a$; its two terms are adjoints supported on opposite blocks, so its squared Frobenius norm is twice the first term's squared norm. Summing proves the identity. An average rejection bound therefore controls an average of squared commutator norms. It does not by itself construct a nearby exactly commuting family, especially for many measurements or a different metric.

A precisely encoded graph consequence

Let $G=(V,E)$ be a finite graph without loops, and encode a $c$-colour assignment by a quantum function with inputs the vertices and outputs $\{1,\ldots,c\}$. Add tests that query the two endpoints of each edge and require different outputs, while retaining all repeat and commutativity tests above. A perfectly passing finite-dimensional strategy exists if and only if $G$ has a proper classical $c$-colouring.

For the nontrivial implication, the preceding proof makes all operators commuting projectors. Their common eigenbasis exists by repeatedly decomposing invariant eigenspaces. At every basis coordinate and every vertex exactly one colour projector has diagonal entry one, defining a deterministic colour for that vertex. The probability of an equal-colour edge is the number of coordinates with that violation divided by $d$, as follows by taking the trace of the two corresponding projectors. Perfect passing means that count is zero for every edge. Thus every coordinate defines a proper colouring; at least one coordinate exists since $d\ge1$. Conversely a proper colouring is a one-dimensional strategy with projectors zero or one and passes every test. Without the added global commutativity tests, this argument does not establish the same equivalence.

Why this does not force an arbitrary prescribed algebra

A commuting family generates a commutative algebra. More explicitly its joint eigenspaces group basis coordinates with identical joint eigenvalues, and the generated unital algebra is isomorphic to $\mathbb C^r$ for the number $r$ of distinct joint patterns. To justify that all pattern indicators lie in the algebra, for any two distinct patterns choose one projector on which they differ; products of that projector or its complement isolate each pattern. The resulting orthogonal idempotents span exactly all functions of the joint pattern. Our test fixes neither $r$ nor the multiplicities of these patterns, and cannot enforce a noncommutative matrix algebra. Tensoring all measurements with an identity preserves every sequential probability, so even exact Hilbert-space dimension cannot be determined from these transcripts.

Audit and remaining gap

The audit checked positivity in the cubic-eigenvalue argument, nonnegative probabilities for every forbidden triple, the factor two in the commutator identity, and the role of added all-pair commutativity in graph colouring. The attempted robust extension stops at small averaged commutators; no rounding theorem to a nearby commuting family or uniform robust graph theorem is proved. The broader source characterization and prescribed-algebra questions remain unresolved. These explicit elementary constructions have no novelty claim, and no experiment or theorem prover was used.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. The coordinating Codex (GPT-6; exact serving revision not exposed) also provided a separate model-assisted written-proof review of this manuscript. This is not independent human verification. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. The construction handles exact projective commutativity and one graph encoding only. No characterization of all tests, robust rounding theorem, or method forcing arbitrary prescribed noncommutative algebras is proved.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Henry Yuen, Noncommutative Property Testing, OWR54/2021 pp.2971–2974; full primary source passage read in cached text, and page2972 operator definition visually checked from the primary PDF. The original agenda, stated known results and convention mismatch are distinguished. https://ems.press/content/serial-article-files/46932.

Final status

Unresolved in this attempt. The construction handles exact projective commutativity and one graph encoding only. No characterization of all tests, robust rounding theorem, or method forcing arbitrary prescribed noncommutative algebras is proved.