English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We study the classical simulatability of commuting quantum circuits with ninput qubits and O(log n) output qubits, where a quantum circuit is classicallysimulatable if its output probability distribution can be sampled up to anexponentially small additive error in classical polynomial time. First, we showthat there exists a commuting quantum circuit that is not classicallysimulatable unless the polynomial hierarchy collapses to the third level. Thisis the first formal evidence that a commuting quantum circuit is notclassically simulatable even when the number of output qubits is exponentiallysmall. Then, we consider a generalized version of the circuit and clarify thecondition under which it is classically simulatable. Lastly, we apply theargument for the above evidence to Clifford circuits in a similar setting andprovide evidence that such a circuit augmented by a depth-1 non-Clifford layeris not classically simulatable. These results reveal subtle differences betweenquantum and classical computation.

Commuting Quantum Circuits with Few Outputs are Unlikely to be Classically Simulatable