Cookies Policy
The website need some cookies and similar means to function. If you permit us, we will use those means to collect data on your visits for aggregated statistics to improve our service. Find out More
Accept Reject
  • Menu
Interest
Topics
Details

Details

  • Name

    Bruno Serra Loff
  • Cluster

    Computer Science
  • Role

    Senior Researcher
  • Since

    01st March 2017
Publications

2022

Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks

Authors
Buhrman, H; Loff, B; Patro, S; Speelman, F;

Publication
13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA.

Abstract
Many computational problems are subject to a quantum speed-up: one might find that a problem having an Opn3q-time or Opn2q-time classic algorithm can be solved by a known Opn1.5q-time or Opnq-time quantum algorithm. The question naturally arises: how much quantum speed-up is possible? The area of fine-grained complexity allows us to prove optimal lower-bounds on the complexity of various computational problems, based on the conjectured hardness of certain natural, well-studied problems. This theory has recently been extended to the quantum setting, in two independent papers by Buhrman, Patro and Speelman [7], and by Aaronson, Chia, Lin, Wang, and Zhang [1]. In this paper, we further extend the theory of fine-grained complexity to the quantum setting. A fundamental conjecture in the classical setting states that the 3SUM problem cannot be solved by (classical) algorithms in time Opn2´eq, for any e a 0. We formulate an analogous conjecture, the Quantum-3SUM-Conjecture, which states that there exist no sublinear Opn1´eq-time quantum algorithms for the 3SUM problem. Based on the Quantum-3SUM-Conjecture, we show new lower-bounds on the time complexity of quantum algorithms for several computational problems. Most of our lower-bounds are optimal, in that they match known upper-bounds, and hence they imply tight limits on the quantum speedup that is possible for these problems. These results are proven by adapting to the quantum setting known classical fine-grained reductions from the 3SUM problem. This adaptation is not trivial, however, since the original classical reductions require pre-processing the input in various ways, e.g. by sorting it according to some order, and this pre-processing (provably) cannot be done in sublinear quantum time. We overcome this bottleneck by combining a quantum walk with a classical dynamic data-structure having a certain “history-independence” property. This type of construction has been used in the past to prove upper bounds, and here we use it for the first time as part of a reduction. This general proof strategy allows us to prove tight lower bounds on several computational-geometry problems, on Convolution-3SUM and on the 0-Edge-Weight-Triangle problem, conditional on the Quantum-3SUM-Conjecture. We believe this proof strategy will be useful in proving tight (conditional) lower-bounds, and limits on quantum speed-ups, for many other problems.

2022

Memory Compression with Quantum Random-Access Gates

Authors
Buhrman, H; Loff, B; Patro, S; Speelman, F;

Publication
17th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2022, July 11-15, 2022, Urbana Champaign, Illinois, USA.

Abstract

2021

Hardness of Constant-round Communication Complexity

Authors
Hirahara, S; Ilango, R; Loff, B;

Publication
36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference).

Abstract

2020

The computational power of parsing expression grammars

Authors
Loff, B; Moreira, N; Reis, R;

Publication
JOURNAL OF COMPUTER AND SYSTEM SCIENCES

Abstract
We study the computational power of parsing expression grammars (PEGs). We begin by constructing PEGs with unexpected behaviour, and surprising new examples of languages with PEGs, including the language of palindromes whose length is a power of two, and a binary-counting language. We then propose a new computational model, the scaffolding automaton, and prove that it exactly characterises the computational power of parsing expression grammars (PEGs). Several consequences will follow from this characterisation: (1) we show that PEGs are computationally “universal”, in a certain sense, which implies the existence of a PEG for a P-complete language; (2) we show that there can be no pumping lemma for PEGs; and (3) we show that PEGs are strictly more powerful than online Turing machines which do o(n/(log?n)2) steps of computation per input symbol. © 2020

2020

Lower Bounds for Semi-adaptive Data Structures via Corruption

Authors
Dvorák, P; Loff, B;

Publication
40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020, December 14-18, 2020, BITS Pilani, K K Birla Goa Campus, Goa, India (Virtual Conference).

Abstract