Trädbredden i en graf är ett användbart kombinatoriskt mått på hur nära grafen är ett träd. Vi bevisar att en kvantkrets med T grindar vars underliggande graf har trädbredd d kan simuleras deterministiskt i. Bland många implikationer visar vi effektiva simuleringar för kvantformler, definierade och studerade av Yao (för loggdjupa kretsar vars portar endast gäller närliggande qubits, en naturlig begränsning som tillfredsställs av de flesta fysiska implementationer. Vi visar också att enkelriktad kvantberäkning av Raussendorf och Briegel (Physical Review Letters, 86:5188-5191, 2001), ett universellt kvantberäkningssystem med lovande fysiska implementationer, effektivt kan simuleras av en randomiserad algoritm om dess kvantresurs härleds från en liten trädbreddskurva.
För kvantkretsmodellen visade Markov & Shi REF att en kvantkrets med n grindar vars underliggande graf har trädbredd tw kan simuleras i O(poly(n)exp(tw) tid.
Simulating quantum computation by contracting tensor networks
{'venue': 'SIAM Journal on Computing', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Physics', 'Computer Science']}