Quantum computation solve some computational problems faster than the best-known alternative in classical computation. The evidence for this consists of examples where a quantum algorithm outperfor ...
How powerful are Quantum Computers? Despite the prevailing belief that Quantum Computers are more powerful than their classical counterparts, this remains a conjecture backed by little formal evidence. Shor's famous factoring algorithm [Shor97] gives an example of a problem that can be solved efficiently on a quantum computer with no known efficient classical algorithm. Factoring, however, is unlikely to be NP-Hard, meaning that few unexpected formal consequences would arise, should such a classical algorithm be discovered. Could it then be the case that any quantum algorithm can be simulated efficiently classically? Likewise, could it be the case that Quantum Computers can quickly solve problems much harder than factoring? If so, where does this power come from, and what classical computational resources do we need to solve the hardest problems for which there exist efficient quantum algorithms? We make progress toward understanding these questions through studying the relationship between classical nondeterminism and quantum computing. In particular, is there a problem that can be solved efficiently on a Quantum Computer that cannot be efficiently solved using nondeterminism? In this thesis we address this problem from the perspective of sampling problems. Namely, we give evidence that approximately sampling the Quantum Fourier Transform of an efficiently computable function, while easy quantumly, is hard for any classical machine in the Polynomial Time Hierarchy. In particular, we prove the existence of a class of distributions that can be sampled efficiently by a Quantum Computer, that likely cannot be approximately sampled in randomized polynomial time with an oracle for the Polynomial Time Hierarchy. Our work complements and generalizes the evidence given in Aaronson and Arkhipov's work [AA2013] where a different distribution with the same computational properties was given. Our result is more general than theirs, but requires a more powerful quantum sampler.
Quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation and, in particular, on problems with an algebraic flavor.
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.