Quantum advantage of unitary Clifford circuits with magic state inputs

DOI10.1098/RSPA.2018.0427MaRDI QIDQ5160656zbMATH OpenOpenAlexWikidataFDO

Authors Mithuna Yoganathan, Richard Jozsa, Sergii Strelchuk

Publication date 29 October 2021

Published in Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.03200, http://europepmc.org/articles/pmc6545052

zbMATH Keywords

complexityquantum computingquantum information theory

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum coherence, entanglement, quantum correlations (81P40)

Abstract: We study the computational power of unitary Clifford circuits with solely magic state inputs (CM circuits), supplemented by classical efficient computation. We show that CM circuits are hard to classically simulate up to multiplicative error (assuming PH non-collapse), and also up to additive error under plausible average-case hardness conjectures. Unlike other such known classes, a broad variety of possible conjectures apply. Along the way we give an extension of the Gottesman-Knill theorem that applies to universal computation, showing that for Clifford circuits with joint stabiliser and non-stabiliser inputs, the stabiliser part can be eliminated in favour of classical simulation, leaving a Clifford circuit on only the non-stabiliser part. Finally we discuss implementational advantages of CM circuits.

Recommendations

• scientific article; zbMATH DE number 7250161
• Classical simulation of quantum computation, the Gottesman-Knill theorem and slightly beyond
• Universal quantum computation with ideal Clifford gates and noisy ancillas
• Classical simulation and complexity of quantum computations (invited talk)
• Invited Talk: Embedding Classical into Quantum Computation

Cited in

(9)

• Complexity of quantum circuits via sensitivity, magic, and coherence
• A magic state’s fidelity can be superior to the operations that created it
• scientific article; zbMATH DE number 7559454 (Why is no real title available?)
• scientific article; zbMATH DE number 7250161 (Why is no real title available?)
• Faster quantum computation with permutations and resonant couplings
• Classically simulating quantum circuits with local depolarizing noise
• Quantifying magic for multi-qubit operations
• Quantum advantage through the magic pentagram problem
• Quantifying magic resource via quantum Jensen-Shannon divergence

This page was built for publication: Quantum advantage of unitary Clifford circuits with magic state inputs

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