![\"\"](\"https:\/\/i0.wp.com\/dabacon.org\/pontiff\/wp-content\/uploads\/2011\/12\/640px-Casa_Mil%C3%A0_-_Barcelona_Spain_-_Jan_2007.jpg?ssl=1\" "\\"Casa")
<\/a><\/p>\nAleksandrs Belovs
\nSpan Programs for Functions with Constant-Sized 1-certificates<\/a>, based on 1105.4024<\/a><\/h3>\nConsider the problem of finding whether or not a triangle exists in a graph with n vertices. Naively using Grover\u2019s algorithm requires time $latex n^{3\/2}$. But a series of improvements have brought this down to $latex n^{10\/7}$ (using Grover with better combinatorics) and $latex n^{13\/10}$ (using element distinctness in a clever way). The current paper reduces this run time to $latex n^{35\/27}$. That is, the exponent is improved from 1.3 to 1.296296296…
\nBefore you roll your eyes and move to another tab, hear me out. The real improvement is in the technique<\/i>, which is radically new, and has applications to many problems; not only triangle-finding.
\nThe idea is to construct something called a learning graph<\/a>. Each vertex is a subset of [n], and (directed) edges are weighted, and correspond to (sets of) queries. These are like randomized decision trees except they can have loops.
\nThe complexity of the resulting algorithm (which we\u2019ll describe below) is a little tricky to define. There is a \u201cnegative complexity\u201d which is simply $latex sum_e w_e$. And a positive complexity which involves maximizing over all yes inputs $latex x$, and then minimizing over all flows of size 1 where the source is the empty set and the sinks are the 1-certificates for $latex x$.
\nAlgorithms in this model correspond to flows of intensity one. The vertex corresponding to the empty set is the root, and 1-certificates (i.e. proofs that x is indeed a yes instance) are the sinks. The cost is $latex sum_e p_e^2\/w_e$, where $latex p$ denotes the flow.
\nFrom a learning graph, there is a recipe to produce a span program, and in turn a quantum query algorithm, with the query complexity equal to the geometric mean of the negative and positive complexities of the learning graph.
\nAs an example, consider the OR function. Here the learning graph is comprised entirely of a root and n leaves. Weight each edge by 1, so the negative complexity is n. If there are k solutions, then the resulting flows are 1\/k on each edge, and so the positive complexity is 1\/k. The algorithm\u2019s complexity is $latex sqrt{n\/k}$. Phew!
\nLess trivial is element distinctness:
\nAre there two indices $latex ineq j$ such that $latex x_i=x_j$?
\nAgain the algorithm achieves the optimal complexity, which is $latex O(n^{2\/3})$, matching Ambainis\u2019s algorithm.
\nThere are lots of new applications too, to improving the triangle runtime, but also getting a bunch of polynomial speedups for other problems that either are, or resemble, subgraph containment. For example, it improves some of the results from 1011.1443<\/a>, and gets linear time algorithms to check whether a graph contains subgraphs from certain families, like lines, T-shaped things, and lines that go through stars.<\/p>\nFrancois le Gall<\/a>,
\nImproved output sensitive quantum algorithms for Boolean matrix multiplication<\/a><\/h3>\nBoolean matrix multiplication means that the matrices are binary, + is replaced by OR, and * is replaced by AND. This arises in many cases, often related to graph theory, such as computing the transitive closure of a graph, triangle-detection, all-pairs shortest path, etc. Also it has application to recognizing context-free languages.
\nThe naive algorithm is $latex O(n^3)$. Reducing to integer multiplication gives $latex O(n^{2.3ldots})$. Quantumly, we can use Grover to compute each entry, for a total runtime of $latex O(n^{2.5})$.
\nBut suppose C has only one nonzero entry. Then we can do recursive Grover search and get time complexity $latex O(n^{1.5})$ [Buhramn Spalek \u201805].
\nIf it has $latex l$ nonzero entries, we get $latex O(n^{1.5}) sqrt l$, neglecting polylogs.
\nThe parameter l represents the sparsity of matrix \u201coutput sensitive algorithms\u201d.
\nIn this work, the runtime is improved to $latex O(n^{3\/2} + nl^{3\/4})$. There is also a more complicated result for query complexity. The techniques are adapted from papers of Williams & Williams, and Lingas. They also make use of a wide range of polynomial speedup tricks: Grover, approximate counting, triangle-detection, etc. The talk leaves the exciting impression that we not yet finished seeing improvements to these techniques.<\/p>\n
Richard Cleve Discrete simulations of continuous-time query algorithms that are efficient with respect to queries, gates and space<\/a>, joint work with Dominic Berry and Sevag Gharibian. <\/h3>\n
After he was introduced, Richard sheepishly admitted, \u201cThe title isn\u2019t really that efficient with its use of space.\u201d
\nNormally the oracle for a quantum query algorithm defines the oracle query by flipping the phase of certain bits. In the continuous-time setting, we can get other phases. So, for example, a \u201dhalf-query\u201d would give $latex Q |x rangle = i^{x_j} | x rangle$, since i is a square root of minus one. In this model, we only charge 1\/2 of a query for this oracle call. More generally, we can have arbitrary fractional queries. Then we can take a limit and get to continuous time to find $latex expbigl(i(H_U + H_Q)tbigr)$ where $latex H_U$ is the driving (gate) Hamiltonian and $latex H_Q$ is a query Hamiltonian.
\nIt is essential to be able to translate from the continuous-time model back to the discrete-time model for algorithmic applications. (cf. The work on NAND trees.) Is there a systematic way to do this translation? Yes, CGMSY-M `09 (improved by LMRSS `11) showed that the query complexity can be directly translated with the same number of queries. But these constructions are not gate efficient. Can we improve the gate complexity of the translation?
\nWe have to be careful because the gate complexity will depend on the complexity of the driving Hamiltonian, so we have to carefully define a notion of approximately implementable Hamiltonian. If we have an epsilon-approximate implementation, and a driving Hamiltonian H, then the number of gates is at least $latex G ge log (|H|)\/epsilon$, where the norm is the operator norm of the Hamiltonian (but modulo some details about the global phase.)
\nMain results<\/u>: We can translate from the continuous-time setting to the discrete-time setting by using:<\/p>\n
\nBefore you roll your eyes and move to another tab, hear me out. The real improvement is in the technique<\/i>, which is radically new, and has applications to many problems; not only triangle-finding.
\nThe idea is to construct something called a learning graph<\/a>. Each vertex is a subset of [n], and (directed) edges are weighted, and correspond to (sets of) queries. These are like randomized decision trees except they can have loops.
\nThe complexity of the resulting algorithm (which we\u2019ll describe below) is a little tricky to define. There is a \u201cnegative complexity\u201d which is simply $latex sum_e w_e$. And a positive complexity which involves maximizing over all yes inputs $latex x$, and then minimizing over all flows of size 1 where the source is the empty set and the sinks are the 1-certificates for $latex x$.
\nAlgorithms in this model correspond to flows of intensity one. The vertex corresponding to the empty set is the root, and 1-certificates (i.e. proofs that x is indeed a yes instance) are the sinks. The cost is $latex sum_e p_e^2\/w_e$, where $latex p$ denotes the flow.
\nFrom a learning graph, there is a recipe to produce a span program, and in turn a quantum query algorithm, with the query complexity equal to the geometric mean of the negative and positive complexities of the learning graph.
\nAs an example, consider the OR function. Here the learning graph is comprised entirely of a root and n leaves. Weight each edge by 1, so the negative complexity is n. If there are k solutions, then the resulting flows are 1\/k on each edge, and so the positive complexity is 1\/k. The algorithm\u2019s complexity is $latex sqrt{n\/k}$. Phew!
\nLess trivial is element distinctness:
\nAre there two indices $latex ineq j$ such that $latex x_i=x_j$?
\nAgain the algorithm achieves the optimal complexity, which is $latex O(n^{2\/3})$, matching Ambainis\u2019s algorithm.
\nThere are lots of new applications too, to improving the triangle runtime, but also getting a bunch of polynomial speedups for other problems that either are, or resemble, subgraph containment. For example, it improves some of the results from 1011.1443<\/a>, and gets linear time algorithms to check whether a graph contains subgraphs from certain families, like lines, T-shaped things, and lines that go through stars.<\/p>\n
Francois le Gall<\/a>,
\nImproved output sensitive quantum algorithms for Boolean matrix multiplication<\/a><\/h3>\nBoolean matrix multiplication means that the matrices are binary, + is replaced by OR, and * is replaced by AND. This arises in many cases, often related to graph theory, such as computing the transitive closure of a graph, triangle-detection, all-pairs shortest path, etc. Also it has application to recognizing context-free languages.
\nThe naive algorithm is $latex O(n^3)$. Reducing to integer multiplication gives $latex O(n^{2.3ldots})$. Quantumly, we can use Grover to compute each entry, for a total runtime of $latex O(n^{2.5})$.
\nBut suppose C has only one nonzero entry. Then we can do recursive Grover search and get time complexity $latex O(n^{1.5})$ [Buhramn Spalek \u201805].
\nIf it has $latex l$ nonzero entries, we get $latex O(n^{1.5}) sqrt l$, neglecting polylogs.
\nThe parameter l represents the sparsity of matrix \u201coutput sensitive algorithms\u201d.
\nIn this work, the runtime is improved to $latex O(n^{3\/2} + nl^{3\/4})$. There is also a more complicated result for query complexity. The techniques are adapted from papers of Williams & Williams, and Lingas. They also make use of a wide range of polynomial speedup tricks: Grover, approximate counting, triangle-detection, etc. The talk leaves the exciting impression that we not yet finished seeing improvements to these techniques.<\/p>\n
Richard Cleve Discrete simulations of continuous-time query algorithms that are efficient with respect to queries, gates and space<\/a>, joint work with Dominic Berry and Sevag Gharibian. <\/h3>\n
After he was introduced, Richard sheepishly admitted, \u201cThe title isn\u2019t really that efficient with its use of space.\u201d
\nNormally the oracle for a quantum query algorithm defines the oracle query by flipping the phase of certain bits. In the continuous-time setting, we can get other phases. So, for example, a \u201dhalf-query\u201d would give $latex Q |x rangle = i^{x_j} | x rangle$, since i is a square root of minus one. In this model, we only charge 1\/2 of a query for this oracle call. More generally, we can have arbitrary fractional queries. Then we can take a limit and get to continuous time to find $latex expbigl(i(H_U + H_Q)tbigr)$ where $latex H_U$ is the driving (gate) Hamiltonian and $latex H_Q$ is a query Hamiltonian.
\nIt is essential to be able to translate from the continuous-time model back to the discrete-time model for algorithmic applications. (cf. The work on NAND trees.) Is there a systematic way to do this translation? Yes, CGMSY-M `09 (improved by LMRSS `11) showed that the query complexity can be directly translated with the same number of queries. But these constructions are not gate efficient. Can we improve the gate complexity of the translation?
\nWe have to be careful because the gate complexity will depend on the complexity of the driving Hamiltonian, so we have to carefully define a notion of approximately implementable Hamiltonian. If we have an epsilon-approximate implementation, and a driving Hamiltonian H, then the number of gates is at least $latex G ge log (|H|)\/epsilon$, where the norm is the operator norm of the Hamiltonian (but modulo some details about the global phase.)
\nMain results<\/u>: We can translate from the continuous-time setting to the discrete-time setting by using:<\/p>\n
\nThe naive algorithm is $latex O(n^3)$. Reducing to integer multiplication gives $latex O(n^{2.3ldots})$. Quantumly, we can use Grover to compute each entry, for a total runtime of $latex O(n^{2.5})$.
\nBut suppose C has only one nonzero entry. Then we can do recursive Grover search and get time complexity $latex O(n^{1.5})$ [Buhramn Spalek \u201805].
\nIf it has $latex l$ nonzero entries, we get $latex O(n^{1.5}) sqrt l$, neglecting polylogs.
\nThe parameter l represents the sparsity of matrix \u201coutput sensitive algorithms\u201d.
\nIn this work, the runtime is improved to $latex O(n^{3\/2} + nl^{3\/4})$. There is also a more complicated result for query complexity. The techniques are adapted from papers of Williams & Williams, and Lingas. They also make use of a wide range of polynomial speedup tricks: Grover, approximate counting, triangle-detection, etc. The talk leaves the exciting impression that we not yet finished seeing improvements to these techniques.<\/p>\n
\nNormally the oracle for a quantum query algorithm defines the oracle query by flipping the phase of certain bits. In the continuous-time setting, we can get other phases. So, for example, a \u201dhalf-query\u201d would give $latex Q |x rangle = i^{x_j} | x rangle$, since i is a square root of minus one. In this model, we only charge 1\/2 of a query for this oracle call. More generally, we can have arbitrary fractional queries. Then we can take a limit and get to continuous time to find $latex expbigl(i(H_U + H_Q)tbigr)$ where $latex H_U$ is the driving (gate) Hamiltonian and $latex H_Q$ is a query Hamiltonian.
\nIt is essential to be able to translate from the continuous-time model back to the discrete-time model for algorithmic applications. (cf. The work on NAND trees.) Is there a systematic way to do this translation? Yes, CGMSY-M `09 (improved by LMRSS `11) showed that the query complexity can be directly translated with the same number of queries. But these constructions are not gate efficient. Can we improve the gate complexity of the translation?
\nWe have to be careful because the gate complexity will depend on the complexity of the driving Hamiltonian, so we have to carefully define a notion of approximately implementable Hamiltonian. If we have an epsilon-approximate implementation, and a driving Hamiltonian H, then the number of gates is at least $latex G ge log (|H|)\/epsilon$, where the norm is the operator norm of the Hamiltonian (but modulo some details about the global phase.)
\nMain results<\/u>: We can translate from the continuous-time setting to the discrete-time setting by using:<\/p>\n