Quantum advantage of unitary Clifford circuits with magic state inputs

DOI10.1098/RSPA.2018.0427zbMATH Open1472.81059arXiv1806.03200OpenAlexW3099009889WikidataQ93001855 ScholiaQ93001855MaRDI QIDQ5160656FDOQ5160656

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)

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.

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

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

zbMATH Keywords

complexityquantum computingquantum information theory

Mathematics Subject Classification ID

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

Cited In (8)

• Faster quantum computation with permutations and resonant couplings
• Quantum advantage through the magic pentagram problem
• Complexity of quantum circuits via sensitivity, magic, and coherence
• Classically simulating quantum circuits with local depolarizing noise
• Quantifying magic for multi-qubit operations
• A magic state’s fidelity can be superior to the operations that created it
• Title not available (Why is that?)
• 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)