Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909940472348672 |
|---|---|
| author | Amy, Matthew Stinchcombe, Lucas Shigeru |
| author_facet | Amy, Matthew Stinchcombe, Lucas Shigeru |
| contents | Implementations of Roetteler's shifted bent function algorithm have in recent years been used to test and benchmark both classical simulation algorithms and quantum hardware. These circuits have many favorable properties, including a tunable amount of non-Clifford resources and a deterministic output, and moreover do not belong to any class of quantum circuits that is known to be efficiently simulable. We show that this family of circuits can in fact be simulated in polynomial time via symbolic path integrals. We do so by endowing symbolic sums with a confluent rewriting system and show that this rewriting system suffices to reduce the circuit's path integral to the hidden shift in polynomial time. We hence resolve an open conjecture about the efficient simulability of this class of circuits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_02778 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums Amy, Matthew Stinchcombe, Lucas Shigeru Quantum Physics Implementations of Roetteler's shifted bent function algorithm have in recent years been used to test and benchmark both classical simulation algorithms and quantum hardware. These circuits have many favorable properties, including a tunable amount of non-Clifford resources and a deterministic output, and moreover do not belong to any class of quantum circuits that is known to be efficiently simulable. We show that this family of circuits can in fact be simulated in polynomial time via symbolic path integrals. We do so by endowing symbolic sums with a confluent rewriting system and show that this rewriting system suffices to reduce the circuit's path integral to the hidden shift in polynomial time. We hence resolve an open conjecture about the efficient simulability of this class of circuits. |
| title | Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2408.02778 |