1 of 44

Noncommutative �Property Testing

Henry Yuen

Columbia University

2 of 44

Overview

Property testing is the study of local-to-global phenomena in theoretical computer science and combinatorics.

This talk: a noncommutative model of property testing.

Towards a systematic study of local-to-global phenomena of quantum functions, whose evaluations are probabilistic, given by measurements on a quantum state.�
Will describe examples of testing quantum functions, including key ingredients of MIP* = RE.�
Many possible questions and avenues to explore.

Local-to-global: you get local views of a big unknown object, what can you say about the global structure of the object?

This talk is about a noncommutative model of property testing, which as far as I can tell has not been defined before. It’s a model to investigate local-to-global phenomena within something I call quantum functions, which are probabilistic functions whose evaluations are given by measurements on a quantum state. I’ll define this formally in a little bit. I will describe a couple interesting examples of testing quantum functions, and I’ll explain how in fact our result MIP* = RE can be formalized as a result about quantum functions.

This is work in progress, and I invite and welcome your thoughts on this topic. I think there are a lot of really interesting questions and avenues to explore.

3 of 44

Classical property testing

4 of 44

Classical properties

5 of 44

The classical model

6 of 44

The classical model

7 of 44

The questions

8 of 44

Linearity testing

Blum-Luby-Rubinfeld (BLR) test

9 of 44

Low-degree testing

Line-vs-Point Low-Degree Test

10 of 44

A noncommutative model

11 of 44

Probabilistic boxes

12 of 44

Probabilistic boxes

13 of 44

Quantum boxes

14 of 44

Quantum functions

15 of 44

Quantum functions

16 of 44

Quantum functions

17 of 44

Quantum functions

18 of 44

Generalization of classical functions

19 of 44

Commutative quantum functions are classical

In other words, commutative quantum functions are equivalent to direct sums of deterministic classical functions!�

20 of 44

Order matters

Queries	Outputs

21 of 44

Order matters

Queries	Outputs

22 of 44

New model, new questions

What does property testing look like in this model?

What can we deduce about internal structure of quantum �functions by probing its inputs and outputs?

What local-to-global phenomena do we have in the noncommutative�setting?

Do classical property testing guarantees lift to quantum setting?

What inherently noncommutative properties can we test?

23 of 44

Linearity testing, revisited

Blum-Luby-Rubinfeld (BLR) test

24 of 44

Magic Square

Unsatisfiable CSP.

Magic Square Test

Reason: There exists a �noncommutative solution to CSP.

25 of 44

Magic Square

Conversely, a MS Operator Solution yields �quantum function that always passes test.

26 of 44

Magic Square

Example of operator solution for Magic Square where��

are Pauli matrices.

27 of 44

Magic Square

Magic Square Test is robust test for Magic Square operator solutions!

Magic Square Test

This theorem (and others like it) is the heart of many results about

Protocols for classically verifying quantum computations (RUV ‘12, CGJV ‘18)
Device-independent randomness expansion/key distribution (CY ‘14, JMS ‘18, Vidick ’18,… )
Complexity of MIP* (NV ‘17, NV ‘18, FJVY ’19, JNVWY ‘20)

28 of 44

Testing larger dimension?

Magic Square is a (robust) test for 4-dim quantum functions.

Tests for higher dimension? Are there tradeoffs between

Dimension guarantee
Efficiency of test (query, computational complexity)
Robustness

	Parallel Magic Square (Coudron-Natarajan 2016, Arnon-Friedman-Y. 2018)
Complexity
Robustness

29 of 44

Testing larger dimension?

Magic Square is a (robust) test for 4-dim quantum functions.

Tests for higher dimension? Are there tradeoffs between

Dimension guarantee
Efficiency of test (query, computational complexity)
Robustness

	Parallel Magic Square (Coudron-Natarajan 2016, Arnon-Friedman-Y. 2018)	2-of-n Magic Square (Chao, Sutherland, Reichardt, Vidick 2017)
Complexity
Robustness

30 of 44

Quantum Low-Degree Test

Quantum Low-Degree Test = Classical Low-Degree Test + Magic Square game

31 of 44

(Classical) Low-degree test, revisited

Line-vs-Point Low-Degree Test

Proof: (at high level) Follows classical analysis of LDT, but with many more complications.

* JNVWY’20 prove result with different test.

32 of 44

Quantum Low-Degree Test

33 of 44

Quantum Low-Degree Test

Quantum Low-Degree Test = Classical Low-Degree Test + Magic Square game

Are there tests with even better tradeoffs between complexity and certified dimension?

For the PCP experts: The great complexity/robustness tradeoff is due to efficiency of classical �low-degree test. Cannot use BLR, because rate of Hadamard code is exponentially worse than �Reed-Muller.

34 of 44

MIP* = RE

35 of 44

Connections with operator algebras

MIP* = RE has consequences for Connes’ Embedding Problem (CEP), which has many a number of equivalent formulations and many consequences in pure mathematics.

36 of 44

Connections with operator algebras

MIP* = RE implies CEP has negative answer.

37 of 44

Future directions

38 of 44

Noncommutative graph properties

39 of 44

Noncommutative graph properties

40 of 44

41 of 44

Classical properties vs. quantum functions

When do classical property tests lift to quantum setting?

When do classical tests retain their robustness?

Example: do testers for locally testable codes force quantum functions to behave classically?

(JNVWY 21) Tensor codes are quantum sound (but parameters can be improved).

Example: analyzing agreement testers on HDX with quantum functions?

42 of 44

Interesting noncommutative properties

Thank You!

43 of 44

Closeness of quantum functions

44 of 44

Closeness of quantum functions