A folk theorem is a mathematical fact that is generally known (at least by experts), even though its proof may never have appeared in print, or may be difficult to locate.  Recently, cstheory user Eli asked for a citation to a proof of the following folk theorem.

If $latex G$ is a graph with maximum degree 3 and is a minor of $latex H$, then $latex G$ is a topological minor of $latex H$.

Wikipedia mentions this to be true, and refers to Reinhard Diestel’s excellent book on graph theory.  Diestel’s book asserts its truth as well, but does not give a proof.

Graph $latex G$ is a minor of graph $latex H$, if $latex G$ can be obtained from $latex H$ by removing edges in $latex H$ and identifying the vertices that were previously the endpoints of the now-deleted edge.  So, in a sense, we can say that $latex H$ “has local structures that looks like” $latex G$ if $latex G$ is a minor of $latex H$.  It is sometimes possible to prove strong properties about the global structure of $latex H$ if we are guaranteed that $latex H$ has no minors of a certain type, because then no local area of $latex H$ can look a certain way, so it is possible to say something about the entire graph.  The most famous example of this is Wagner’s Theorem, which states that a graph is planar iff neither $latex K_5$ nor $latex K_{3,3}$ is a minor of it.

A topological minor is a related notion.  Informally, $latex G$ is a topological minor of $latex H$ if we can start with $latex G$, and transform it into a subgraph of $latex H$ by only adding vertices into edges that already exist (i.e., subdividing edges, so edge $latex (u,v)$ becomes two edges, $latex (u,x)$ and $latex (x,v)$).  Figure 1 on this web page shows examples of a minor and a topological minor.  (Note: that figure may be behind a paywall.  If anyone knows a good diagram explaining minor vs. topological minor that is freely available, please put it in the comments.)

Fortunately for Eli, Robin Kothari and co-authors had needed this folk theorem for a paper, and they had been unable to find a proof of it either, so they reproved it themselves.  Kothari’s proof (and answer to Eli’s question) appears here.  It is an example of a growing number of original proofs that appear on cstheory.  That proof by Kothari is definitely my “favorite answer of the week.”  As Eli put it, “This is stellar.”

How hard is it to answer a question? As theoretical computer scientists, this query haunts us. We formalize a ‘question’ as a function on some input and ‘answering’ as running a finite procedure. This procedure might run on a Turing Machine, your cellphone, or a quantum computer. ‘Hard’ is quantified by use of resources such as energy, space or time. Unfortunately, the most popular notion of hardness — time complexity — is notoriously difficult to characterize in a quantum computing model. If we want to show what a model of computation can and can’t do, we must use a related, but simpler measure of complexity. For quantum computing this measure is quantum query complexity. This post explains quantum query complexity and lays the foundations for future entries that will introduce the lower bound technique of the (negative) adversary method, and show how it characterizes quantum query complexity through its connection to span programs.

In the query model, the input to our algorithm is given as a black-box (called the oracle). We can only gain knowledge about the input by asking the oracle for individual bits. The input is a bit-string \( x \in D \subseteq \{0, 1\}^n \) and the goal is to compute some function \(f : D \rightarrow \{0,1\}\). If \(D = \{0,1\}^n\) then we call the function total. For simplicity, we only consider decision problems (binary range), although the machinery has been developed for functions over finite strings in arbitrary finite input and output alphabets.

The query complexity of a function is the minimum number of queries used by any circuit computing the function. For a two-sided error \(\epsilon\), we denote the query complexity by \(Q_\epsilon(f)\). Since success amplification is straightforward, we abbreviate further by setting \(Q(f) = Q_{1/3}(f)\). Similar measures exist for classical algorithms, where this model is more frequently referred to as decision-tree complexity. The usual notation is \(D(f)\) for deterministic query complexity, \(R(f)\) for two-sided error (\(1/3\)) randomized query complexity, and \(C(f)\) for certificate (or non-deterministic) complexity. We specify our model concretely, following [HS05]:

Quantum query model: formally

The memory of a quantum query algorithm is described by three Hilbert spaces (registers): the input register, \(H_I\), which holds the input \(x \in D\), the query register, \(H_Q\), which holds an integer \(1 \leq i \leq n\) and a bit \(b \in \{0,1\}\), and the working memory, \(H_W\), which holds an arbitrary value. The query register and working memory together form the memory accessible to the algorithm, denoted \(H_A\). The unitaries that define the algorithm can only act on this space. The accessible memory of a quantum query algorithm is initialized to a fixed state. On input \(x\) the initial state of the algorithm is \(|x\rangle_I \otimes |1, 0\rangle_Q \otimes |0\rangle_W\). The state of the algorithm then evolves through queries, which depend on the input register, and accessible memory operators which do not.

A query is a unitary operator where the oracle answer is given in the phase. We definite the operator \(O\) by its action on the basis state \(|x\rangle_I \otimes |i,b\rangle_Q\) as

\[ O |x\rangle_I \otimes |i,b\rangle_Q = (-1)^{bx_i} |x\rangle_I \otimes |i,b\rangle_Q \]

The accessible memory operator is an arbitrary unitary operation \(U\) on the accessible memory \(H_A\). This operation is extended to act on the whole space by interpreting it as \(I_I \otimes U\) and \(O\) is interpreted as \(O \otimes I_W\). Thus the state of the algorithm on input \(x\) after \(t\) queries can be written as:

\[ |x\rangle_I |\psi^t_x\rangle_A = U_t O U_{t-1} … U_1 O U_0 |x\rangle_I |1, 0\rangle_Q |0\rangle_W \]

Where we noticed that the input register is left unchanged by the algorithm. The output of a \(T\)-query algorithm is distributed according to the state of the accessible memory \(|\psi^T_x\rangle\) and two projections \(\Pi_0\) and \(\Pi_1\) such that \(\Pi_0 + \Pi_1 = I\) corresponding to the possible outcomes of a decision problem. The probability that given input \(x\) the algorithm returns \(0\) is \(||\Pi_0|\psi^T_x\rangle||^2\) and \(1\) is \(||\Pi_1|\psi^T_x\rangle||^2\). \(Q_\epsilon(f)\) is the minimum number of queries made by an algorithm which outputs \(f(x)\) with probability \(1 – \epsilon\) for every \(x\).

Relations between models

For partial functions, the quantum query complexity can be exponentially smaller than randomized or deterministic query complexity [Sho95, BV97, Sim97, Aar10]. However, if the partial function is invariant under permuting inputs and outputs then the complexities are polynomially related with \(R(f) = O(Q(f)^9)\) [AA09]. If the function is total, then \(D(f)\) is bounded by \(O(Q(f)^6)\) , \(O(Q(f)^4)\) for monotone total functions, and \(O(Q(f)^2)\) for symmetric total functions [BBC+01]. However, no greater than quadratic separations are known for total functions (this separation is achieved by \(OR\), for example). This has led to the conjecture that for total functions \(D(f) = O(Q(f)^2)\). This conjecture is open for all classes of total functions, except monotone [BBC+01], read-once [BS04], and constant-sized 1-certificate functions.

The infamous time complexity is always at least as large as the query complexity since each query takes one unit step. For famous algorithms such as Grover’s search [Gro96] and Shor’s period finding (which is the quantum part of his famed polynomial time factoring algorithm) [Sho95], the time complexity is within poly-logarithmic factors of the query complexity. There are also exceptions to the tight correspondence. The Hidden Subgroup Problem has polynomial query complexity [EHK04], yet polynomial time algorithms are not known for the problem.

By taking the computation between queries as free, we get a handle for producing lower bounds. This allows us to develop strong information-theoretic techniques for lower bounding quantum query complexity. In my next post I will use this framework to develop the (negative) adversary method.

References

[AA09] Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups. 2009, arXiv:0911.0996v1 [quant-ph].

[Aar10] Scott Aaronson. BQP and the polynomial hierarchy. In Proceedings of the 42nd ACM symposium on Theory of computing, pages 141-150. ACM, 2010, arXiv:0910.4698 [quant-ph].

[BBC+01] R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf. Quantum lower bounds by polynomials. Journal of the ACM (JACM), 48(4):778-797, 2001.

[BS04] H. Barnum, and M. Saks. A lower bound on the quantum query complexity of read-once functions. Journal of Computer and System Sciences, 69(2):244-258, 2004. arXiv:quant-ph/0201007v1

[BV97] E. Bernstein and U. Vazirani. Quantum complexity theory. SIAM J. Comput., 26(5):1411-1473, 1997.

[EHK04] M. Ettinger, P. Hoyer, and E. Knill. The quantum query complexity of the hidden subgroup problem is polynomial. Information Processing Letters, 91(1):43-48, 2004, arXiv:quant-ph/0401083v1.

[Gro96] L.K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212-219. ACM, 1996, arXiv:quant-ph/9605043.

[HS05] P. Hoyer, and R. Spalek. Lower Bounds on Quantum Query Complexity. Bulletin of the European Association for Theoretical Computer Science, 87, 2005. arXiv:quant-ph/0509153v1.

[Sim97] D.R. Simon. On the power of quantum computation. SIAM Journal on Computing, 26:1474, 1997.

[Sho95] P.W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26:1484-1509, 1995, arXiv:quant-ph/9508027.

The question-and-answer site cstheory, also known as “Theoretical Computer Science,” was founded in 2010 by community volunteers, and now has over 4500 registered users.  Some of the founding members of cstheory participated in discussion of a proposed solution to the P/NP problem that spanned multiple blogs, led to the creation of wiki pages, and brought together researchers in disparate areas from around the world.  This effort made it clear that the worldwide theoretical computer science community was ready for – and needed – a structured way to ask research-level questions and to consider answers to such questions.  (For more background on cstheory, please see this SIGACT News article.)

This blog is intended for community discussion of topics in theoretical computer science, broadly construed.  While the blog’s parent site (cstheory) requires that questions asked there be “research-level” (e.g., not elementary), posts and comments here can have a wider scope.  We hope to publish both introductory and advanced posts in complexity theory, learning theory, quantum computing, programming language theory, logic, algorithms, and other areas of theory, and theory applied to practice.

We are actively soliciting one-time contributions, and the participation of regular contributors.  If you would like to participate in the blog, please email one of the editors — Joe Fitzsimons or Aaron Sterling — or post your interest on the blog contributor signup sheet.

Editors’ bios:

Aaron Sterling is a PhD candidate in computer science at Iowa State University.  He is currently a Visiting Predoctoral Fellow at Northwestern University, working with Ming-Yang Kao on the theory of self-assembly.  He authors the blog Nanoexplanations.

Joe Fitzsimons recieved his DPhil from the from the University of Oxford in 2007, and is currently research assistant professor at the Centre for Quantum Technologies, at the National University of Singapore, and a visiting lecturer at University College Dublin. Prior to joining CQT, Joe spent 3 years as a Junior Research Fellow at Merton College, Oxford, and as a visiting researcher at the Institute for Quantum Computing and the department of Combinatorics and Optimization at the University of Waterloo. His research interests lie mainly in the field of quantum computation.