Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1311.3610 · Lecture notes in computer science

Entanglement, Flow and Classical Simulatability in Measurement Based Quantum Computation

Damian Markham, Elham Kashefi

Published Jan 1, 2014• 11 citations
arXivHTMLPDF
DOI
10.1007/978-3-319-06880-0_22

Related papers

Flow of information and classical simulatability in MBQC and Adiabatic QC

Damian Markham

•Dec 1, 2013•0 citations

Bound entanglement in measurement based quantum computation

克樹 小西

•Sep 1, 2022•0 citations

The Role of Classical Computation in Measurement-Based Quantum Computation

Dan E. Browne, Janet Anders

Springer eBooks•Jun 10, 2008•0 citations

Computational quantum-classical boundary of noisy commuting quantum circuits

Keisuke Fujii, Shuhei Tamate

It is often said that the transition from quantum to classical worlds is caused by decoherence originated from an interaction between a system of interest and its surrounding environment. Here we establish a computational quantum-classical boundary from the viewpoint of classical simulatability of a quantum system under decoherence. Specifically, we consider commuting quantum circuits being subject to decoherence. Or equivalently, we can regard them as measurement-based quantum computation on decohered weighted graph states. To show intractability of classical simulation in the quantum side, we utilize the postselection argument and crucially strengthen it by taking noise effect into account. Classical simulatability in the classical side is also shown constructively by using both separable criteria in a projected-entangled-pair-state picture and the Gottesman-Knill theorem for mixed state Clifford circuits. We found that when each qubit is subject to a single-qubit complete-positive-trace-preserving noise, the computational quantum-classical boundary is sharply given by the noise rate required for the distillability of a magic state. The obtained quantum-classical boundary of noisy quantum dynamics reveals a complexity landscape of controlled quantum systems. This paves a way to an experimentally feasible verification of quantum mechanics in a high complexity limit beyond classically simulatable region.

arXiv:1406.6932•Scientific Reports•May 18, 2016•25 citations

Measurement-based quantum computation

Hans J. Briegel, Dan E. Browne, Wolfgang Dür +2 more

arXiv:0910.1116•Nature Physics•Jan 1, 2009•1,162 citations

Computational quantum-classical boundary of commuting quantum circuits

Keisuke Fujii, Shuhei Tamate

It is often said that the transition from quantum to classical worlds is caused by decoherence originated from an interaction between a system of interest and its surrounding environment. Here we establish a computational quantum-classical boundary from the viewpoint of classical simulatability of a quantum system under decoherence. Specifically, we consider commuting quantum circuits being subject to decoherence. Or equivalently, we can regard them as measurement-based quantum computation on decohered weighted graph states. To show intractability of classical simulation above the boundary, we utilize the postselection argument introduced by M. J. Bremner, R. Jozsa, and D. J. Shepherd [Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science 465, 1413 (2009).] and crucially strengthen its statement by taking noise effect into account. Classical simulatability below the boundary is also shown constructively by using both separable criteria in a projected-entangled-pair-state picture and the Gottesman-Knill theorem for mixed state Clifford circuits. We found that when each qubit is subject to a single-qubit complete-positive-trace-preserving noise, the computational quantum-classical boundary is sharply given by the noise rate required for the distillability of a magic state. The obtained quantum-classical boundary of noisy quantum dynamics reveals a complexity landscape of controlled quantum systems. This paves a way to an experimentally feasible verification of quantum mechanics in a high complexity limit beyond classically simulatable region.

•Jun 26, 2014•0 citations
It is often said that the transition from quantum to classical worlds is caused by decoherence originated from an interaction between a system of interest and its surrounding environment. Here we establish a computational quantum-classical boundary from the viewpoint of classical simulatability of a quantum system under decoherence. Specifically, we consider commuting quantum circuits being subject to decoherence. Or equivalently, we can regard them as measurement-based quantum computation on decohered weighted graph states. To show intractability of classical simulation in the quantum side, we utilize the postselection argument and crucially strengthen it by taking noise effect into account. Classical simulatability in the classical side is also shown constructively by using both separable criteria in a projected-entangled-pair-state picture and the Gottesman-Knill theorem for mixed state Clifford circuits. We found that when each qubit is subject to a single-qubit complete-positive-trace-preserving noise, the computational quantum-classical boundary is sharply given by the noise rate required for the distillability of a magic state. The obtained quantum-classical boundary of noisy quantum dynamics reveals a complexity landscape of controlled quantum systems. This paves a way to an experimentally feasible verification of quantum mechanics in a high complexity limit beyond classically simulatable region.
It is often said that the transition from quantum to classical worlds is caused by decoherence originated from an interaction between a system of interest and its surrounding environment. Here we establish a computational quantum-classical boundary from the viewpoint of classical simulatability of a quantum system under decoherence. Specifically, we consider commuting quantum circuits being subject to decoherence. Or equivalently, we can regard them as measurement-based quantum computation on decohered weighted graph states. To show intractability of classical simulation above the boundary, we utilize the postselection argument introduced by M. J. Bremner, R. Jozsa, and D. J. Shepherd [Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science 465, 1413 (2009).] and crucially strengthen its statement by taking noise effect into account. Classical simulatability below the boundary is also shown constructively by using both separable criteria in a projected-entangled-pair-state picture and the Gottesman-Knill theorem for mixed state Clifford circuits. We found that when each qubit is subject to a single-qubit complete-positive-trace-preserving noise, the computational quantum-classical boundary is sharply given by the noise rate required for the distillability of a magic state. The obtained quantum-classical boundary of noisy quantum dynamics reveals a complexity landscape of controlled quantum systems. This paves a way to an experimentally feasible verification of quantum mechanics in a high complexity limit beyond classically simulatable region.