Measurement based computation and computational complexity
Richard Jozsa
University of Bristol, United Kingdom.
Abstract: It is well known that measurement based quantum computation (MQC) is polynomially equivalent as a computational model to the standard gate array model. Nevertheless it provides novel perspectives and benefits of computational complexity when we consider more subtle complexity measures than just time complexity (total sequential running time). In particular MQC naturally incorporates a fundamental feature of parallelisability of algorithms, not present in the gate array model and leads to a new notion of separating an algorithm into classical and quantum parts. In this talk we will discuss and illustrate these issues.