Quantum advantage through the magic pentagram problem

DOI10.1007/s11128-022-03684-6OpenAlexW4297996516MaRDI QIDQ2104768

Haesol Han, Minjin Choi, Soojoon Lee, Jeonghyeon Shin, Byungchan Kim

Publication date: 7 December 2022

Published in: Quantum Information Processing (Search for Journal in Brave)

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

zbMATH Keywords

quantum algorithmsquantum advantage\(\mathbf{NC^0}\)\(\mathbf{QNC^0}\)magic pentagram gamemagic pentagram problemshallow circuits

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum games (91A81)

Cites Work

• Quantum pseudo-telepathy
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Simple unified form for the major no-hidden-variables theorems
• Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
• Quantum advantage with shallow circuits

This page was built for publication: Quantum advantage through the magic pentagram problem