Interactive shallow Clifford circuits: Quantum advantage against NC¹ and beyond

DOI10.1145/3357713.3384332MaRDI QIDQ5144973zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Grier, Luke Schaeffer

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.02555

zbMATH Keywords

classical simulationClifford circuitsconstant-depthinteractive protocolsmeasurement-based computationquantum advantagerelation problems

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(9)

• Mapping NCV Circuits to Optimized Clifford+T Circuits
• 3XOR games with perfect commuting operator strategies have perfect tensor product strategies and are decidable in polynomial time
• Quantum advantage from one-way functions
• Quantum and classical communication complexity of permutation-invariant functions
• Parity vs. \(\text{AC}^0\) with simple quantum preprocessing
• Noisy decoding by shallow circuits with parities: classical and quantum (extended abstract)
• Bridging resource theory and quantum key distribution: geometric analysis and statistical testing
• On the fine-grained query complexity of symmetric functions
• On the fine-grained query complexity of symmetric functions

This page was built for publication: Interactive shallow Clifford circuits: Quantum advantage against NC¹ and beyond

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144973)