Zobrazeno 1 - 10
of 18
pro vyhledávání: '"Theory of computation → Quantum query complexity"'
Autor:
Magniez, Frédéric, Nayak, Ashwin
Publikováno v:
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Jul 2020, Saarbrücken, Germany. pp.82:1--82:18, ⟨10.4230/LIPIcs.ICALP.2020.82⟩
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Jul 2020, Saarbrücken, Germany. pp.82:1--82:18, ⟨10.4230/LIPIcs.ICALP.2020.82⟩
Set Disjointness on a Line is a variant of the Set Disjointness problem in a distributed computing scenario with $d+1$ processors arranged on a path of length $d$. It was introduced by Le Gall and Magniez (PODC 2018) for proving lower bounds on the q
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::eddb5ca8968ce1f9e9470360a7958b69
https://doi.org/10.1145/3512751
https://doi.org/10.1145/3512751
We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable time search with complexity O(√Tlog n) where T = ∑_{i = 1}ⁿ t_i² w
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2b4e34cfe3a8dbba0ac08756a533e2a0
Autor:
Beame, Paul, Kornerup, Niels
Cumulative memory -- the sum of space used per step over the duration of a computation -- is a fine-grained measure of time-space complexity that was introduced to analyze cryptographic applications like password hashing. It is a more accurate cost m
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3b7cf9d6da80b77f8b886760afbb2795
Autor:
Fawzi, Omar, Walter, Michael
LIPIcs, Volume 266, TQC 2023, Complete Volume
LIPIcs, Vol. 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023), pages 1-314
LIPIcs, Vol. 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023), pages 1-314
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2731b3761d9f5d936b5b809fa39dcc54
Autor:
Ambainis, Andris, Belovs, Aleksandrs
While it is known that there is at most a polynomial separation between quantum query complexity and the polynomial degree for total functions, the precise relationship between the two is not clear for partial functions. In this paper, we demonstrate
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::80eaf569554b1e7c42d9ed35bda2943c
We present a quantum algorithm for sampling an edge on a path between two nodes s and t in an undirected graph given as an adjacency matrix, and show that this can be done in query complexity that is asymptotically the same, up to log factors, as the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e4916817f138d2961915827588b178ba
Autor:
Fawzi, Omar, Walter, Michael
Front Matter, Table of Contents, Preface, Conference Organization
LIPIcs, Vol. 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023), pages 0:i-0:xii
LIPIcs, Vol. 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023), pages 0:i-0:xii
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::0c341b3fb305388442bb8992c57aa7d6
The Aaronson-Ambainis conjecture (Theory of Computing '14) says that every low-degree bounded polynomial on the Boolean hypercube has an influential variable. This conjecture, if true, would imply that the acceptance probability of every $d$-query qu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6bff9c69df14c9faceb61b4359c0c528
https://doi.org/10.4230/lipics.ccc.2022.28
https://doi.org/10.4230/lipics.ccc.2022.28
We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index i such that x_i≠ y_i, in a z
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f36d59a4fb73b00c711d84ac96aeedb1
Autor:
Montanaro, Ashley, Shao, Changpeng
We study the problem of learning an unknown graph provided via an oracle using a quantum algorithm. We consider three query models. In the first model ("OR queries"), the oracle returns whether a given subset of the vertices contains any edges. In th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::fdd91fec8f85f77bcf0173e27a97ddb8