Magic and Communication Complexity
We establish novel connections between magic in quantum circuits and communication complexity. In particular, we show that functions computable with low magic have low communication cost.
Authors
- Alex May (ORCID: https://orcid.org/0000-0002-4030-5410)
- Henry Yuen
- Uma Girish
- Natalie Parham
Institutions
- Perimeter Institute (CA)
- Columbia University (US)
Publication Details
- Published
- 2026-06-09
- DOI
- https://doi.org/10.1145/3798129.3800799
- Primary Topic
- Cultural Differences and Values
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- National Science Foundation
- Alfred P. Sloan Foundation
- Government of Canada
- Industry Canada
- Institut Périmètre de physique théorique
- Ministry of Colleges and Universities
- Air Force Office of Scientific Research