Symmetric quantum computation
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908577723056128 |
|---|---|
| author | Castro-Silva, Davi Gur, Tom Strelchuk, Sergii |
| author_facet | Castro-Silva, Davi Gur, Tom Strelchuk, Sergii |
| contents | We introduce a systematic study of "symmetric quantum circuits", a new restricted model of quantum computation that preserves the symmetries of the problems it solves. This model is well-adapted for studying the role of symmetry in quantum speedups, extending a central notion of symmetric computation studied in the classical setting.
Our results establish that symmetric quantum circuits are fundamentally more powerful than their classical counterparts. First, we give efficient symmetric circuits for key quantum techniques such as amplitude amplification, phase estimation and linear combination of unitaries. In addition, we show how the task of symmetric state preparation can be performed efficiently in several natural cases. Finally, we demonstrate an exponential separation in the symmetric setting for the problem XOR-SAT, which requires exponential-size symmetric classical circuits but can be solved by polynomial-size symmetric quantum circuits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_01214 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Symmetric quantum computation Castro-Silva, Davi Gur, Tom Strelchuk, Sergii Quantum Physics Computational Complexity We introduce a systematic study of "symmetric quantum circuits", a new restricted model of quantum computation that preserves the symmetries of the problems it solves. This model is well-adapted for studying the role of symmetry in quantum speedups, extending a central notion of symmetric computation studied in the classical setting. Our results establish that symmetric quantum circuits are fundamentally more powerful than their classical counterparts. First, we give efficient symmetric circuits for key quantum techniques such as amplitude amplification, phase estimation and linear combination of unitaries. In addition, we show how the task of symmetric state preparation can be performed efficiently in several natural cases. Finally, we demonstrate an exponential separation in the symmetric setting for the problem XOR-SAT, which requires exponential-size symmetric classical circuits but can be solved by polynomial-size symmetric quantum circuits. |
| title | Symmetric quantum computation |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2501.01214 |