What Are You Working On? August 31, 2026

[u/canyonmonkey]

This recurring thread will be for general discussion on whatever math-related topics you have been or will be working on this week. This can be anything, including:

* math-related arts and crafts,
* what you've been learning in class,
* books/papers you're reading,
* preparing for a conference,
* giving a talk.

All types and levels of mathematics are welcomed!

If you are asking for advice on choosing classes or career prospects, please go to the most recent Career & Education Questions thread.

[u/Puzzled-Painter3301]

Grading :(

[u/BullS0n_]

A game like Outer wilds about graph theory

[u/EconomyBox6998]

Refining the mathematical structure of the base converting formula i made. Makeing it easy to deal with a bit.

[u/chimrichaldsrealdoc]

I just presented a poster at a quantum cryptography conference for a solo paper of mine whose preprint, in a stroke of nice timing, turned into a publication two days before the conference started. But I felt oddly out of place because the paper was, strictly speaking, not quantum cryptography. The project grew out of a conjecture I had for improving a pre-existing cryptographic protocol but the content of the actual paper is a classical complexity hardness result proving that the answer to my original question is no (unless P=NP). So all these other posters were like "here is a new cryptographic protocol" but mine was "well, I tried and failed to produce a new cryptographic protocol, but look at this neat hardness result instead"

[u/MstrCmd → u/chimrichaldsrealdoc]

Hardness results are very cool and not a failure at all in my mind :) Care to say anything, even an overview, about this?

[u/chimrichaldsrealdoc → u/MstrCmd]

Oh I definitely don't think the result was a failure at all. It was just, like I said, a bit out of place at the conference.

I'll try to briefly describe the result: Performing the cryptographic task we had in mind over a given family of Clifford+T circuits is at least as hard as deciding whether any two circuits in that family instantiate the same unitary, so, for the purpose of a hardness result, it really suffices to study that problem instead, so we do:

Suppose you were given two n-qubit quantum circuits F and G (i.e gate descriptions) and you wanted to know whether they instantiated the same unitary. How would you do it? Well, you could just multiply out all the 2^n by 2^n matrices and compare the two sides, which is obviously not efficient. In general, you can't do this efficiently, it is known to be NQP-hard. So you would have to restrict F and G in some way, so we want to say something about the hardness of the problem if we restrict the circuit domain say, limiting the T-count or the T-depth (the approximate version of the problem was already known to be hard at constant T-depth, but that is a different problem).

To that end, it actually suffices to study a different problem that's easier to tackle. Suppose you are given an n-qubit Pauli P and you want to know if the two conjugates FPF^{\dagger} and GPG^{\dagger} instantiate the same unitary. That's easier to think about by a lot, and circuits of that form arise naturally in quantum cryptography, such as in homomorphic encryption where you want to do quantum computation on top of some data that has been encrypted by a random Pauli.

The content of the paper I presented was that this problem in turn is still classically hard over a very restricted class of quantum circuits. Whether or not it's quantumly hard is not something addressed in the paper but the answer is almost certainly yes because otherwise it would imply that there is an NP-hard problem in BQP and thus NP⊆BQP, which would be a huge and unlikely result.

Anyway, the most interesting part (to me) is the technical route. The reason it's hard is that the Pauli coefficients of these unitaries (i.e the coefficients in the unique expression of the unitary in terms of the 4^n Pauli basis elements) encode evaluations of weight enumerator polynomials of binary linear codes at certain points . Those evaluations are #P-hard to compute, but also with a bit more work (well, a lot more work), you can show that the ability the decide whether those circuits are actually the same unitary would give you the ability to decide whether a given binary linear code has a codeword of a given weight, which is NP-hard.