Quantum circuits: power and limitations
Steven Thomas Homer, Debajyoti Bera · 2010
Quantum computation was proposed as an alternate computing process in the late-20th century, when classical computing models faced limitation in solving quantum mechanical problems. Major breakthroughs came in the 1990s, when quantum algorithms for integer factoring and black-box searching were invented that are faster than the best classical algorithms known even today. In this thesis, we look at quantum circuits with limited depth and size and analyse their power and limitations. Computer Science is about the study of computational problems, many of which are motivated by real-world applications. We are interested as much in an actual method to solve a problem as in its unsolvability. In computational complexity theory we separate out the actual problem from the computing apparatus (e.g. a Turing machine, an AND-OR circuit) and analyse the hardness of the computation, due both to the intrinsic complexity of the problem and to the underlying model. In this thesis, we consider quantum circuits built with a universal set of gates and show that non-constant depth is required to compute a particular function (parity) and other similar functions. The parity function, extensively studied previously, was shown to take non-constant depth for classical circuits too, thus providing an evidence of an inherent hardness in the function itself. On the other hand we show that the quantum circuit model is rich enough to build a universal circuit (one circuit that can simulate all circuits) that has roughly the same depth or size as the simulated circuit. We also consider a fault model in which some of the inputs to a gate might not be connected to the gate's output. We ask if we can detect the faulty inputs by testing the gate on different inputs. Our goal is to minimise the number of tests. We show that this is very hard for general gates but for certain gates it can be provably easier to detect faulty inputs. We even show that quantum algorithms can provably outperform classical algorithms for these gates. These results give us a sense of wherein lies the power of quantum computation and quantum circuits in particular.