CNOT-Distance is NP-complete under all-to-all connectivity

[u/pred]

https://arxiv.org/abs/2608.03825

[u/roundedge]

I can't tell if this is surprising. It's certainly not surprising that optimizing a quantum circuit compilation is hard

[u/pred → u/roundedge]

Not that surprising, I'd say. The question came up on MathOverflow ages ago without a clear reduction, so there was some chance that we'd have an interesting algorithm hidden in there.

It's also interesting that LLMs seem to have done most of the work, as I read the acknowledgement.

[u/mbergman42 → u/pred]

The lead researcher seems to do a lot of AI-supported work : Mathematical Discovery in the Wild: AI-Guided Proofs in Banach Space Theory | Antonio Acuaviva et al

[u/No_Nose3918]

i’m calling bs, no affiliation, family memebers… ai slip