Ugo Marzolino —	University of Ljubljana #
Computational complexity of matrix product states and matrix product operators #
I study matrix product states (MPS) and matrix product operators (MPO) from the point of view of 
computational complexity. MPS are pure states whose coefficients in an orthonormal tensor basis are 
transition amplitudes in an auxiliary, virtual Hilbert space, while MPO are operators with coefficients in 
an orthonormal operator tensor basis being represented as trantion amplitudes in an auxiliary Hilbert 
space. In particular, I show that measuring transition amplitudes of MPS or expectations of local 
operators of density matrices described by a MPO allows to encode, in the auxiliary space, quantum 
circuits with the additional power of general linear operators, and thus solve very hard computational 
problems. I will exemplify the above result with cluster state (MPS) and steady states of boundary 
dissipated quantum spin chains (MPO). This result deepens the knowledge of hardly implementable quantum 
problems. As a byproduct of the above construction and after a very short introduction to complexity 
classes, I prove an important result of computational complexity. The latter states that quantum Turing 
machine with postselection and bounded error probability with subroutines, that exactly solve problems 
probabilistically solvable by the same type of machine, can be simulated without the exact subroutines. 
This result, together with the equivalence between quantum Turing machine with postselection and bounded 
error probability and probabilistic Turing machines with unbounded error probability, implies the collapse 
of a hierarchy of classical computational classes that was not yet proven.