Optimising T-count is NP-hard
| Authors |
|
|---|---|
| Publication date | 12-09-2023 |
| Edition | v1 |
| Number of pages | 3 |
| Publisher | ArXiv |
| Organisations |
|
| Abstract | n this short note we show that Boolean satisfiability reduces to finding the optimal number of T gates of a quantum circuit, and hence that optimising T-count is NP-hard. |
| Document type | Preprint |
| Note | Version v2 (2023) and v3 (2024) are also available on ArXiv |
| Language | English |
| Published at |
https://doi.org/10.48550/arXiv.2310.05958
(Final published version)
|
| Downloads |
2310.05958v1
(Final published version)
|
| Permalink to this page | |
