5 Search Results for "Brassard, Gilles"

Document
DOI: 10.4230/LIPIcs.STACS.2021.19
A Framework of Quantum Strong Exponential-Time Hypotheses

Authors: Harry Buhrman, Subhasree Patro, and Florian Speelman

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
The strong exponential-time hypothesis (SETH) is a commonly used conjecture in the field of complexity theory. It essentially states that determining whether a CNF formula is satisfiable can not be done faster than exhaustive search over all possible assignments. This hypothesis and its variants gave rise to a fruitful field of research, fine-grained complexity, obtaining (mostly tight) lower bounds for many problems in P whose unconditional lower bounds are very likely beyond current techniques. In this work, we introduce an extensive framework of Quantum Strong Exponential-Time Hypotheses, as quantum analogues to what SETH is for classical computation. Using the QSETH framework, we are able to translate quantum query lower bounds on black-box problems to conditional quantum time lower bounds for many problems in P. As an example, we provide a conditional quantum time lower bound of Ω(n^1.5) for the Longest Common Subsequence and Edit Distance problems. We also show that the n² SETH-based lower bound for a recent scheme for Proofs of Useful Work carries over to the quantum setting using our framework, maintaining a quadratic gap between verifier and prover. Lastly, we show that the assumptions in our framework can not be simplified further with relativizing proof techniques, as they are false in relativized worlds.
Cite as

Harry Buhrman, Subhasree Patro, and Florian Speelman. A Framework of Quantum Strong Exponential-Time Hypotheses. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.STACS.2021.19,
  author =	{Buhrman, Harry and Patro, Subhasree and Speelman, Florian},
  title =	{{A Framework of Quantum Strong Exponential-Time Hypotheses}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.19},
  URN =		{urn:nbn:de:0030-drops-136642},
  doi =		{10.4230/LIPIcs.STACS.2021.19},
  annote =	{Keywords: complexity theory, fine-grained complexity, longest common subsequence, edit distance, quantum query complexity, strong exponential-time hypothesis}
}
Document
DOI: 10.4230/LIPIcs.TQC.2019.4
The RGB No-Signalling Game

Authors: Xavier Coiteux-Roy and Claude Crépeau

Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)

Abstract
Introducing the simplest of all No-Signalling Games: the RGB Game where two verifiers interrogate two provers, Alice and Bob, far enough from each other that communication between them is too slow to be possible. Each prover may be independently queried one of three possible colours: Red, Green or Blue. Let a be the colour announced to Alice and b be announced to Bob. To win the game they must reply colours x (resp. y) such that a != x != y != b. This work focuses on this new game mainly as a pedagogical tool for its simplicity but also because it triggered us to introduce a new set of definitions for reductions among multi-party probability distributions and related non-locality classes. We show that a particular winning strategy for the RGB Game is equivalent to the PR-Box of Popescu-Rohrlich and thus No-Signalling. Moreover, we use this example to define No-Signalling in a new useful way, as the intersection of two natural classes of multi-party probability distributions called one-way signalling. We exhibit a quantum strategy able to beat the classical local maximum winning probability of 8/9 shifting it up to 11/12. Optimality of this quantum strategy is demonstrated using the standard tool of semidefinite programming.
Cite as

Xavier Coiteux-Roy and Claude Crépeau. The RGB No-Signalling Game. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{coiteuxroy_et_al:LIPIcs.TQC.2019.4,
  author =	{Coiteux-Roy, Xavier and Cr\'{e}peau, Claude},
  title =	{{The RGB No-Signalling Game}},
  booktitle =	{14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-112-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{135},
  editor =	{van Dam, Wim and Man\v{c}inska, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.4},
  URN =		{urn:nbn:de:0030-drops-103965},
  doi =		{10.4230/LIPIcs.TQC.2019.4},
  annote =	{Keywords: No-Signalling, Quantum Entanglement, Non-Locality, Bell inequality, Semidefinite Programming, Non-locality Hierarchy}
}
Document
DOI: 10.4230/LIPIcs.TQC.2017.3
Provably Secure Key Establishment Against Quantum Adversaries

Authors: Aleksandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, and Louis Salvail

Published in: LIPIcs, Volume 73, 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)

Abstract
At Crypto 2011, some of us had proposed a family of cryptographic protocols for key establishment capable of protecting quantum and classical legitimate parties unconditionally against a quantum eavesdropper in the query complexity model. Unfortunately, our security proofs were unsatisfactory from a cryptographically meaningful perspective because they were sound only in a worst-case scenario. Here, we extend our results and prove that for any \eps > 0, there is a classical protocol that allows the legitimate parties to establish a common key after O(N) expected queries to a random oracle, yet any quantum eavesdropper will have a vanishing probability of learning their key after O(N^(1.5-\eps)) queries to the same oracle. The vanishing probability applies to a typical run of the protocol. If we allow the legitimate parties to use a quantum computer as well, their advantage over the quantum eavesdropper becomes arbitrarily close to the quadratic advantage that classical legitimate parties enjoyed over classical eavesdroppers in the seminal 1974 work of Ralph Merkle. Along the way, we develop new tools to give lower bounds on the number of quantum queries required to distinguish two probability distributions. This method in itself could have multiple applications in cryptography. We use it here to study average-case quantum query complexity, for which we develop a new composition theorem of independent interest.
Cite as

Aleksandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, and Louis Salvail. Provably Secure Key Establishment Against Quantum Adversaries. In 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 73, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{belovs_et_al:LIPIcs.TQC.2017.3,
  author =	{Belovs, Aleksandrs and Brassard, Gilles and H{\o}yer, Peter and Kaplan, Marc and Laplante, Sophie and Salvail, Louis},
  title =	{{Provably Secure Key Establishment Against Quantum Adversaries}},
  booktitle =	{12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-034-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{73},
  editor =	{Wilde, Mark M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2017.3},
  URN =		{urn:nbn:de:0030-drops-85816},
  doi =		{10.4230/LIPIcs.TQC.2017.3},
  annote =	{Keywords: Merkle puzzles, Key establishment schemes, Quantum cryptography, Adversary method, Average-case analysis}
}
Document
DOI: 10.4230/LIPIcs.TQC.2014.7
Exact Classical Simulation of the GHZ Distribution

Authors: Gilles Brassard, Luc Devroye, and Claude Gravel

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)

Abstract
John Bell has shown that the correlations entailed by quantum mechanics cannot be reproduced by a classical process involving non-communicating parties. But can they be simulated with the help of bounded communication? This problem has been studied for more than twenty years and it is now well understood in the case of bipartite entanglement. However, the issue was still widely open for multipartite entanglement, even for the simplest case, which is the tripartite Greenberger-Horne-Zeilinger (GHZ) state. We give an exact simulation of arbitrary independent von Neumann measurements on general n-partite GHZ states. Our protocol requires O(n^2) bits of expected communication between the parties, and O(n*log(n)) expected time is sufficient to carry it out in parallel. Furthermore, we need only an expectation of O(n) independent unbiased random bits, with no need for the generation of continuous real random variables nor prior shared random variables. In the case of equatorial measurements, we improve earlier results with a protocol that needs only O(n*log(n)) bits of communication and O(log^2(n)) parallel time. At the cost of a slight increase in the number of bits communicated, these tasks can be accomplished with a constant expected number of rounds.
Cite as

Gilles Brassard, Luc Devroye, and Claude Gravel. Exact Classical Simulation of the GHZ Distribution. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 7-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{brassard_et_al:LIPIcs.TQC.2014.7,
  author =	{Brassard, Gilles and Devroye, Luc and Gravel, Claude},
  title =	{{Exact Classical Simulation of the GHZ Distribution}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{7--23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.7},
  URN =		{urn:nbn:de:0030-drops-48025},
  doi =		{10.4230/LIPIcs.TQC.2014.7},
  annote =	{Keywords: Entanglement simulation, Greenberger-Horne-Zeilinger (GHZ) state, Multiparty entanglement, von Neumann's rejection algorithm, Knuth-Yao's sampling alg}
}
Document
DOI: 10.4230/DagSemRep.210
Quantum Algorithms (Dagstuhl Seminar 98191)

Authors: Thomas Beth and Gilles Brassard

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Thomas Beth and Gilles Brassard. Quantum Algorithms (Dagstuhl Seminar 98191). Dagstuhl Seminar Report 210, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (1998)

Copy BibTex To Clipboard

@TechReport{beth_et_al:DagSemRep.210,
  author =	{Beth, Thomas and Brassard, Gilles},
  title =	{{Quantum Algorithms (Dagstuhl Seminar 98191)}},
  pages =	{1--21},
  ISSN =	{1619-0203},
  year =	{1998},
  type = 	{Dagstuhl Seminar Report},
  number =	{210},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.210},
  URN =		{urn:nbn:de:0030-drops-150966},
  doi =		{10.4230/DagSemRep.210},
}
  • Refine by Author
  • 3 Brassard, Gilles
  • 1 Belovs, Aleksandrs
  • 1 Beth, Thomas
  • 1 Buhrman, Harry
  • 1 Coiteux-Roy, Xavier
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Problems, reductions and completeness
  • 1 Theory of computation → Quantum complexity theory
  • 1 Theory of computation → Quantum information theory

  • Refine by Keyword
  • 1 Adversary method
  • 1 Average-case analysis
  • 1 Bell inequality
  • 1 Entanglement simulation
  • 1 Greenberger-Horne-Zeilinger (GHZ) state
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 1998
  • 1 2014
  • 1 2018
  • 1 2019
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact