BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

François Le Gall

François Le Gall appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phComputational ComplexityData Structures and AlgorithmsDistributed, Parallel, and Cluster ComputingInformation Theorymath.ITDatabasesmath.GR

Catalog footprint

What is connected

13works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2024arXiv

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture

The Quantum Singular Value Transformation (QSVT) is a recent technique that gives a unified framework to describe most quantum algorithms discovered so far, and may lead to the development of novel quantum algorithms. In this paper we investigate the hardness of classically simulating the QSVT. A recent result by Chia, Gilyén, Li, Lin, Tang and Wang (STOC 2020) showed that the QSVT can be efficiently "dequantized" for low-rank matrices, and discussed its implication to quantum machine learning. In this work, motivated by establishing the superiority of quantum algorithms for quantum chemistry and making progress on the quantum PCP conjecture, we focus on the other main class of matrices considered in applications of the QSVT, sparse matrices. We first show how to efficiently "dequantize", with arbitrarily small constant precision, the QSVT associated with a low-degree polynomial. We apply this technique to design classical algorithms that estimate, with constant precision, the singular values of a sparse matrix. We show in particular that a central computational problem considered by quantum algorithms for quantum chemistry (estimating the ground state energy of a local Hamiltonian when given, as an additional input, a state sufficiently close to the ground state) can be solved efficiently with constant precision on a classical computer. As a complementary result, we prove that with inverse-polynomial precision, the same problem becomes BQP-complete. This gives theoretical evidence for the superiority of quantum algorithms for chemistry, and strongly suggests that said superiority stems from the improved precision achievable in the quantum setting. We also discuss how this dequantization technique may help make progress on the central quantum PCP conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Quantum Advantage with Shallow Circuits Under Arbitrary Corruption

Recent works by Bravyi, Gosset and König (Science 2018), Bene Watts et al. (STOC 2019), Coudron, Stark and Vidick (QIP 2019) and Le Gall (CCC 2019) have shown unconditional separations between the computational powers of shallow (i.e., small-depth) quantum and classical circuits: quantum circuits can solve in constant depth computational problems that require logarithmic depth to solve with classical circuits. Using quantum error correction, Bravyi, Gosset, König and Tomamichel (Nature Physics 2020) further proved that a similar separation still persists even if quantum circuits are subject to local stochastic noise. In this paper, we consider the case where any constant fraction of the qubits (for instance, huge blocks of qubits) may be arbitrarily corrupted at the end of the computation. We make a first step forward towards establishing a quantum advantage even in this extremely challenging setting: we show that there exists a computational problem that can be solved in constant depth by a quantum circuit but such that even solving any large subproblem of this problem requires logarithmic depth with bounded fan-in classical circuits. This gives another compelling evidence of the computational power of quantum shallow circuits. In order to show our result, we consider the Graph State Sampling problem (which was also used in prior works) on expander graphs. We exploit the "robustness" of expander graphs against vertex corruption to show that a subproblem hard for small-depth classical circuits can still be extracted from the output of the corrupted quantum circuit.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Quantum Distributed Algorithms for Detection of Cliques

The possibilities offered by quantum computing have drawn attention in the distributed computing community recently, with several breakthrough results showing quantum distributed algorithms that run faster than the fastest known classical counterparts, and even separations between the two models. A prime example is the result by Izumi, Le Gall, and Magniez [STACS 2020], who showed that triangle detection by quantum distributed algorithms is easier than triangle listing, while an analogous result is not known in the classical case. In this paper we present a framework for fast quantum distributed clique detection. This improves upon the state-of-the-art for the triangle case, and is also more general, applying to larger clique sizes. Our main technical contribution is a new approach for detecting cliques by encapsulating this as a search task for nodes that can be added to smaller cliques. To extract the best complexities out of our approach, we develop a framework for nested distributed quantum searches, which employ checking procedures that are quantum themselves. Moreover, we show a circuit-complexity barrier on proving a lower bound of the form $Ω(n^{3/5+ε})$ for $K_p$-detection for any $p \geq 4$, even in the classical (non-quantum) distributed CONGEST setting.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs

In this paper we give fast distributed graph algorithms for detecting and listing small subgraphs, and for computing or approximating the girth. Our algorithms improve upon the state of the art by polynomial factors, and for girth, we obtain an constant-time algorithm for additive +1 approximation in the Congested Clique, and the first parametrized algorithm for exact computation in CONGEST. In the Congested Clique, we develop a technique for learning small neighborhoods, and apply it to obtain an $O(1)$-round algorithm that computes the girth with only an additive +1 error. Next, we introduce a new technique (the partition tree technique) allowing for efficiently and deterministically listing all copies of any subgraph, improving upon the state-of the-art for non-dense graphs. We give two applications of this technique: First we show that for constant $k$, $C_{2k}$-detection can be solved in $O(1)$ rounds in the Congested Clique, improving on prior work which used matrix multiplication and had polynomial round complexity. Second, we show that in triangle-free graphs, the girth can be exactly computed in time polynomially faster than the best known bounds for general graphs. In CONGEST, we describe a new approach for finding cycles, and apply it in two ways: first we show a fast parametrized algorithm for girth with round complexity $\tilde{O}(\min(g\cdot n^{1-1/Θ(g)},n))$ for any girth $g$; and second, we show how to find small even-length cycles $C_{2k}$ for $k = 3,4,5$ in $O(n^{1-1/k})$ rounds, which is a polynomial improvement upon the previous running times. Finally, using our improved $C_6$-freeness algorithm and the barrier on proving lower bounds on triangle-freeness of Eden et al., we show that improving the current $\tildeΩ(\sqrt{n})$ lower bound for $C_6$-freeness of Korhonen et al. by any polynomial factor would imply strong circuit complexity lower bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Quantum Speedup for the Minimum Steiner Tree Problem

A recent breakthrough by Ambainis, Balodis, Iraids, Kokainis, Prūsis and Vihrovs (SODA'19) showed how to construct faster quantum algorithms for the Traveling Salesman Problem and a few other NP-hard problems by combining in a novel way quantum search with classical dynamic programming. In this paper, we show how to apply this approach to the minimum Steiner tree problem, a well-known NP-hard problem, and construct the first quantum algorithm that solves this problem faster than the best known classical algorithms. More precisely, the complexity of our quantum algorithm is $\mathcal{O}(1.812^k\poly(n))$, where $n$ denotes the number of vertices in the graph and $k$ denotes the number of terminals. In comparison, the best known classical algorithm has complexity $\mathcal{O}(2^k\poly(n))$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Group and Color Isomorphism Problems

In this paper, we prove results on the relationship between the complexity of the group and color isomorphism problems. The difficulty of color isomorphism problems is known to be closely linked to the the composition factors of the permutation group involved. Previous works are primarily concerned with applying color isomorphism to bou nded degree graph isomorphism, and have therefore focused on the alternating composit ion factors, since those are the bottleneck in the case of graph isomorphism. We consider the color isomorphism problem with composition factors restricted to those other than the alternating group, show that group isomorphism reduces in n^(O(log log n)) time to this problem, and, conversely, that a special case of this color isomorphism problem reduces to a slight generalization of group isomorphism. We then sharpen our results by identifying the projective special linear group as the main obstacle to faster algorithms for group isomorphism and prove that the aforementioned reduc tion from group isomorphism to color isomorphism in fact produces only cyclic and projective special linear factors. Our results demonstrate that, just as the alternatin g group was a barrier to faster algorithms for graph isomorphism for three decades, the projective special linear group is an obstacle to faster algorithms for group isomorphism.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Quantum Communication Complexity of Distributed Set Joins

Computing set joins of two inputs is a common task in database theory. Recently, Van Gucht, Williams, Woodruff and Zhang [PODS 2015] considered the complexity of such problems in the natural model of (classical) two-party communication complexity and obtained tight bounds for the complexity of several important distributed set joins. In this paper we initiate the study of the *quantum* communication complexity of distributed set joins. We design a quantum protocol for distributed Boolean matrix multiplication, which corresponds to computing the composition join of two databases, showing that the product of two $n\times n$ Boolean matrices, each owned by one of two respective parties, can be computed with $\widetilde{O}(\sqrt{n}\ell^{3/4})$ qubits of communication, where $\ell$ denotes the number of non-zero entries of the product. Since Van Gucht et al. showed that the classical communication complexity of this problem is $\widetildeΘ(n\sqrt{\ell})$, our quantum algorithm outperforms classical protocols whenever the output matrix is sparse. We also show a quantum lower bound and a matching classical upper bound on the communication complexity of distributed matrix multiplication over $\mathbb{F}_2$. Besides their applications to database theory, the communication complexity of set joins is interesting due to its connections to direct product theorems in communication complexity. In this work we also introduce a notion of *all-pairs* product theorem, and relate this notion to standard direct product theorems in communication complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Solving Laplacian Systems in Logarithmic Space

We investigate the space complexity of solving linear systems of equations. While all known deterministic or randomized algorithms solving a square system of $n$ linear equations in $n$ variables require $Ω(\log^2 n)$ space, Ta-Shma (STOC 2013) recently showed that on a quantum computer an approximate solution can be computed in logarithmic space, giving the first explicit computational task for which quantum computation seems to outperform classical computation with respect to space complexity. In this paper we show that for systems of linear equations in the Laplacian matrix of graphs, the same logarithmic space complexity can actually be achieved by a classical (i.e., non-quantum) algorithm. More precisely, given a system of linear equations $Lx=b$, where $L$ is the (normalized) Laplacian matrix of a graph on $n$ vertices and $b$ is a unit-norm vector, our algorithm outputs a vector $\tilde x$ such that $\left\lVert\tilde x -x\right\rVert\le 1/\mathrm{poly}(n)$ and uses only $O(\log n)$ space if the underlying graph has polynomially bounded weights. We also show how to estimate, again in logarithmic space, the smallest non-zero eigenvalue of $L$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Quantum Algorithms for Finding Constant-sized Sub-hypergraphs

We develop a general framework to construct quantum algorithms that detect if a $3$-uniform hypergraph given as input contains a sub-hypergraph isomorphic to a prespecified constant-sized hypergraph. This framework is based on the concept of nested quantum walks recently proposed by Jeffery, Kothari and Magniez [SODA'13], and extends the methodology designed by Lee, Magniez and Santha [SODA'13] for similar problems over graphs. As applications, we obtain a quantum algorithm for finding a $4$-clique in a $3$-uniform hypergraph on $n$ vertices with query complexity $O(n^{1.883})$, and a quantum algorithm for determining if a ternary operator over a set of size $n$ is associative with query complexity $O(n^{2.113})$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete

This paper presents stronger methods of achieving perfect completeness in quantum interactive proofs. First, it is proved that any problem in QMA has a two-message quantum interactive proof system of perfect completeness with constant soundness error, where the verifier has only to send a constant number of halves of EPR pairs. This in particular implies that the class QMA is necessarily included by the class QIP_1(2) of problems having two-message quantum interactive proofs of perfect completeness, which gives the first nontrivial upper bound for QMA in terms of quantum interactive proofs. It is also proved that any problem having an $m$-message quantum interactive proof system necessarily has an $(m+1)$-message quantum interactive proof system of perfect completeness. This improves the previous result due to Kitaev and Watrous, where the resulting system of perfect completeness requires $m+2$ messages if not using the parallelization result.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Reconstructing Strings from Substrings with Quantum Queries

This paper investigates the number of quantum queries made to solve the problem of reconstructing an unknown string from its substrings in a certain query model. More concretely, the goal of the problem is to identify an unknown string $S$ by making queries of the following form: "Is $s$ a substring of $S$?", where $s$ is a query string over the given alphabet. The number of queries required to identify the string $S$ is the query complexity of this problem. First we show a quantum algorithm that exactly identifies the string $S$ with at most $3/4N + o(N)$ queries, where $N$ is the length of $S$. This contrasts sharply with the classical query complexity $N$. Our algorithm uses Skiena and Sundaram's classical algorithm and the Grover search as subroutines. To make them effectively work, we develop another subroutine that finds a string appearing only once in $S$, which may have an independent interest. We also prove two lower bounds. The first one is a general lower bound of $Ω(\frac{N}{\log^2{N}})$, which means we cannot achieve a query complexity of $O(N^{1-ε})$ for any constant $ε$. The other one claims that if we cannot use queries of length roughly between $\log N$ and $3 \log N$, then we cannot achieve a query complexity of any sublinear function in $N$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Constructing Quantum Network Coding Schemes from Classical Nonlinear Protocols

The k-pair problem in network coding theory asks to send k messages simultaneously between k source-target pairs over a directed acyclic graph. In a previous paper [ICALP 2009, Part I, pages 622--633] the present authors showed that if a classical k-pair problem is solvable by means of a linear coding scheme, then the quantum k-pair problem over the same graph is also solvable, provided that classical communication can be sent for free between any pair of nodes of the graph. Here we address the main case that remained open in our previous work, namely whether nonlinear classical network coding schemes can also give rise to quantum network coding schemes. This question is motivated by the fact that there are networks for which there are no linear solutions to the k-pair problem, whereas nonlinear solutions exist. In the present paper we overcome the limitation to linear protocols and describe a new communication protocol for perfect quantum network coding that improves over the previous one as follows: (i) the new protocol does not put any condition on the underlying classical coding scheme, that is, it can simulate nonlinear communication protocols as well, and (ii) the amount of classical communication sent in the protocol is significantly reduced.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

General Scheme for Perfect Quantum Network Coding with Free Classical Communication

This paper considers the problem of efficiently transmitting quantum states through a network. It has been known for some time that without additional assumptions it is impossible to achieve this task perfectly in general -- indeed, it is impossible even for the simple butterfly network. As additional resource we allow free classical communication between any pair of network nodes. It is shown that perfect quantum network coding is achievable in this model whenever classical network coding is possible over the same network when replacing all quantum capacities by classical capacities. More precisely, it is proved that perfect quantum network coding using free classical communication is possible over a network with $k$ source-target pairs if there exists a classical linear (or even vector linear) coding scheme over a finite ring. Our proof is constructive in that we give explicit quantum coding operations for each network node. This paper also gives an upper bound on the number of classical communication required in terms of $k$, the maximal fan-in of any network node, and the size of the network.

0 citations0 reviewsNo code linkedOpen access