Search Results

Documents authored by Klauck, Hartmut

Document
DOI: 10.4230/LIPIcs.MFCS.2021.69
The Power of One Clean Qubit in Communication Complexity

Authors: Hartmut Klauck and Debbie Lim

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We study quantum communication protocols, in which the players' storage starts out in a state where one qubit is in a pure state, and all other qubits are totally mixed (i.e. in a random state), and no other storage is available (for messages or internal computations). This restriction on the available quantum memory has been studied extensively in the model of quantum circuits, and it is known that classically simulating quantum circuits operating on such memory is hard when the additive error of the simulation is exponentially small (in the input length), under the assumption that the polynomial hierarchy does not collapse. We study this setting in communication complexity. The goal is to consider larger additive error for simulation-hardness results, and to not use unproven assumptions. We define a complexity measure for this model that takes into account that standard error reduction techniques do not work here. We define a clocked and a semi-unclocked model, and describe efficient simulations between those. We characterize a one-way communication version of the model in terms of weakly unbounded error communication complexity. Our main result is that there is a quantum protocol using one clean qubit only and using O(log n) qubits of communication, such that any classical protocol simulating the acceptance behaviour of the quantum protocol within additive error 1/poly(n) needs communication Ω(n). We also describe a candidate problem, for which an exponential gap between the one-clean-qubit communication complexity and the randomized communication complexity is likely to hold, and hence a classical simulation of the one-clean-qubit model within constant additive error might be hard in communication complexity. We describe a geometrical conjecture that implies the lower bound.
Cite as

Hartmut Klauck and Debbie Lim. The Power of One Clean Qubit in Communication Complexity. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 69:1-69:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{klauck_et_al:LIPIcs.MFCS.2021.69,
  author =	{Klauck, Hartmut and Lim, Debbie},
  title =	{{The Power of One Clean Qubit in Communication Complexity}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{69:1--69:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.69},
  URN =		{urn:nbn:de:0030-drops-145097},
  doi =		{10.4230/LIPIcs.MFCS.2021.69},
  annote =	{Keywords: Quantum Complexity Theory, Quantum Communication Complexity, One Clean Qubit Model}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.15
The Complexity of Quantum Disjointness

Authors: Hartmut Klauck

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
We introduce the communication problem QNDISJ, short for Quantum (Unique) Non-Disjointness, and study its complexity under different modes of communication complexity. The main motivation for the problem is that it is a candidate for the separation of the quantum communication complexity classes QMA and QCMA. The problem generalizes the Vector-in-Subspace and Non-Disjointness problems. We give tight bounds for the QMA, quantum, randomized communication complexities of the problem. We show polynomially related upper and lower bounds for the MA complexity. We also show an upper bound for QCMA protocols, and show that the bound is tight for a natural class of QCMA protocols for the problem. The latter lower bound is based on a geometric lemma, that states that every subset of the n-dimensional sphere of measure 2^-p must contain an ortho-normal set of points of size Omega(n/p). We also study a "small-spaces" version of the problem, and give upper and lower bounds for its randomized complexity that show that the QNDISJ problem is harder than Non-disjointness for randomized protocols. Interestingly, for quantum modes the complexity depends only on the dimension of the smaller space, whereas for classical modes the dimension of the larger space matters.
Cite as

Hartmut Klauck. The Complexity of Quantum Disjointness. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{klauck:LIPIcs.MFCS.2017.15,
  author =	{Klauck, Hartmut},
  title =	{{The Complexity of Quantum Disjointness}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.15},
  URN =		{urn:nbn:de:0030-drops-81010},
  doi =		{10.4230/LIPIcs.MFCS.2017.15},
  annote =	{Keywords: Communication Complexity, Quantum Proof Systems}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.544
Correlation in Hard Distributions in Communication Complexity

Authors: Ralph Christian Bottesch, Dmitry Gavinsky, and Hartmut Klauck

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
We study the effect that the amount of correlation in a bipartite distribution has on the communication complexity of a problem under that distribution. We introduce a new family of complexity measures that interpolates between the two previously studied extreme cases: the (standard) randomised communication complexity and the case of distributional complexity under product distributions. - We give a tight characterisation of the randomised complexity of Disjointness under distributions with mutual information k, showing that it is Theta(sqrt(n(k+1))) for all 0 <= k <= n. This smoothly interpolates between the lower bounds of Babai, Frankl and Simon for the product distribution case (k=0), and the bound of Razborov for the randomised case. The upper bounds improve and generalise what was known for product distributions, and imply that any tight bound for Disjointness needs Omega(n) bits of mutual information in the corresponding distribution. - We study the same question in the distributional quantum setting, and show a lower bound of Omega((n(k+1))^{1/4}), and an upper bound (via constructing communication protocols), matching up to a logarithmic factor. - We show that there are total Boolean functions f_d that have distributional communication complexity O(log(n)) under all distributions of information up to o(n), while the (interactive) distributional complexity maximised over all distributions is Theta(log(d)) for n <= d <= 2^{n/100}. This shows, in particular, that the correlation needed to show that a problem is hard can be much larger than the communication complexity of the problem. - We show that in the setting of one-way communication under product distributions, the dependence of communication cost on the allowed error epsilon is multiplicative in log(1/epsilon) - the previous upper bounds had the dependence of more than 1/epsilon. This result, for the first time, explains how one-way communication complexity under product distributions is stronger than PAC-learning: both tasks are characterised by the VC-dimension, but have very different error dependence (learning from examples, it costs more to reduce the error).
Cite as

Ralph Christian Bottesch, Dmitry Gavinsky, and Hartmut Klauck. Correlation in Hard Distributions in Communication Complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 544-572, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{bottesch_et_al:LIPIcs.APPROX-RANDOM.2015.544,
  author =	{Bottesch, Ralph Christian and Gavinsky, Dmitry and Klauck, Hartmut},
  title =	{{Correlation in Hard Distributions in Communication Complexity}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{544--572},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.544},
  URN =		{urn:nbn:de:0030-drops-53234},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.544},
  annote =	{Keywords: communication complexity; information theory}
}
Document
DOI: 10.4230/DagRep.5.2.109
Limitations of Convex Programming: Lower Bounds on Extended Formulations and Factorization Ranks (Dagstuhl Seminar 15082)

Authors: Hartmut Klauck, Troy Lee, Dirk Oliver Theis, and Rekha R. Thomas

Published in: Dagstuhl Reports, Volume 5, Issue 2 (2015)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 15082 "Limitations of convex programming: lower bounds on extended formulations and factorization ranks" held in February 2015. Summaries of a selection of talks are given in addition to a list of open problems raised during the seminar.
Cite as

Hartmut Klauck, Troy Lee, Dirk Oliver Theis, and Rekha R. Thomas. Limitations of Convex Programming: Lower Bounds on Extended Formulations and Factorization Ranks (Dagstuhl Seminar 15082). In Dagstuhl Reports, Volume 5, Issue 2, pp. 109-127, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{klauck_et_al:DagRep.5.2.109,
  author =	{Klauck, Hartmut and Lee, Troy and Theis, Dirk Oliver and Thomas, Rekha R.},
  title =	{{Limitations of Convex Programming: Lower Bounds on Extended Formulations and Factorization Ranks (Dagstuhl Seminar 15082)}},
  pages =	{109--127},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{2},
  editor =	{Klauck, Hartmut and Lee, Troy and Theis, Dirk Oliver and Thomas, Rekha R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.2.109},
  URN =		{urn:nbn:de:0030-drops-50480},
  doi =		{10.4230/DagRep.5.2.109},
  annote =	{Keywords: Convex optimization, extended formulations, cone rank, positive semidefinite rank, nonnegative rank, quantum communication complexity, real algebraic geometry}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2014.481
New Bounds for the Garden-Hose Model

Authors: Hartmut Klauck and Supartha Podder

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract
We show new results about the garden-hose model. Our main results include improved lower bounds based on non-deterministic communication complexity (leading to the previously unknown Theta(n) bounds for Inner Product mod 2 and Disjointness), as well as an O(n * log^3(n) upper bound for the Distributed Majority function (previously conjectured to have quadratic complexity). We show an efficient simulation of formulae made of AND, OR, XOR gates in the garden-hose model, which implies that lower bounds on the garden-hose complexity GH(f) of the order Omega(n^{2+epsilon}) will be hard to obtain for explicit functions. Furthermore we study a time-bounded variant of the model, in which even modest savings in time can lead to exponential lower bounds on the size of garden-hose protocols.
Cite as

Hartmut Klauck and Supartha Podder. New Bounds for the Garden-Hose Model. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 481-492, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{klauck_et_al:LIPIcs.FSTTCS.2014.481,
  author =	{Klauck, Hartmut and Podder, Supartha},
  title =	{{New Bounds for the Garden-Hose Model}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{481--492},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.481},
  URN =		{urn:nbn:de:0030-drops-48657},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.481},
  annote =	{Keywords: Space Complexity, Communication Complexity, Garden-Hose Model}
}
Document
DOI: 10.4230/DagRep.3.2.127
Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices (Dagstuhl Seminar 13082)

Authors: LeRoy B. Beasley, Hartmut Klauck, Troy Lee, and Dirk Oliver Theis

Published in: Dagstuhl Reports, Volume 3, Issue 2 (2013)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 13082 "Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices".
Cite as

LeRoy B. Beasley, Hartmut Klauck, Troy Lee, and Dirk Oliver Theis. Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices (Dagstuhl Seminar 13082). In Dagstuhl Reports, Volume 3, Issue 2, pp. 127-143, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{beasley_et_al:DagRep.3.2.127,
  author =	{Beasley, LeRoy B. and Klauck, Hartmut and Lee, Troy and Theis, Dirk Oliver},
  title =	{{Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices (Dagstuhl Seminar 13082)}},
  pages =	{127--143},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{3},
  number =	{2},
  editor =	{Beasley, LeRoy B. and Klauck, Hartmut and Lee, Troy and Theis, Dirk Oliver},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.2.127},
  URN =		{urn:nbn:de:0030-drops-40191},
  doi =		{10.4230/DagRep.3.2.127},
  annote =	{Keywords: nonnegative rank, combinatorial optimization, communication complexity, extended formulation size}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.424
Fooling One-Sided Quantum Protocols

Authors: Hartmut Klauck and Ronald de Wolf

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
We use the venerable "fooling set" method to prove new lower bounds on the quantum communication complexity of various functions. Let f : X x Y -> {0,1} be a Boolean function, fool^1(f) its maximal fooling set size among 1-inputs, Q_1^*(f) its one-sided-error quantum communication complexity with prior entanglement, and NQ(f) its nondeterministic quantum communication complexity (without prior entanglement; this model is trivial with shared randomness or entanglement). Our main results are the following, where logs are to base 2: - If the maximal fooling set is "upper triangular" (which is for instance the case for the equality, disjointness, and greater-than functions), then we have Q_1^*(f) >= 1/2 log fool^1(f) - 1/2, which (by superdense coding) is essentially optimal for functions like equality, disjointness, and greater-than. No super-constant lower bound for equality seems to follow from earlier techniques. - For all f we have Q_1^*(f) >= 1/4 log fool^1(f) - 1/2. - NQ(f) >= 1/2 log fool^1(f) + 1. We do not know if the factor 1/2 is needed in this result, but it cannot be replaced by 1: we give an example where NQ(f) \approx 0.613 log fool^1(f).
Cite as

Hartmut Klauck and Ronald de Wolf. Fooling One-Sided Quantum Protocols. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 424-433, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{klauck_et_al:LIPIcs.STACS.2013.424,
  author =	{Klauck, Hartmut and de Wolf, Ronald},
  title =	{{Fooling One-Sided Quantum Protocols}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{424--433},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.424},
  URN =		{urn:nbn:de:0030-drops-39539},
  doi =		{10.4230/LIPIcs.STACS.2013.424},
  annote =	{Keywords: Quantum computing, communication complexity, fooling set, lower bound}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.148
New bounds on the classical and quantum communication complexity of some graph properties

Authors: Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, and Ronald de Wolf

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
We study the communication complexity of a number of graph properties where the edges of the graph G are distributed between Alice and Bob (i.e., each receives some of the edges as input). Our main results are: 1. An Omega(n) lower bound on the quantum communication complexity of deciding whether an n-vertex graph G is connected, nearly matching the trivial classical upper bound of O(n log n) bits of communication. 2. A deterministic upper bound of O(n^{3/2} log n) bits for deciding if a bipartite graph contains a perfect matching, and a quantum lower bound of Omega(n) for this problem. 3. A Theta(n^2) bound for the randomized communication complexity of deciding if a graph has an Eulerian tour, and a Theta(n^{3/2}) bound for its quantum communication complexity. 4. The first two quantum lower bounds are obtained by exhibiting a reduction from the n-bit Inner Product problem to these graph problems, which solves an open question of Babai, Frankl and Simon [Babai et al 1986]. The third quantum lower bound comes from recent results about the quantum communication complexity of composed functions. We also obtain essentially tight bounds for the quantum communication complexity of a few other problems, such as deciding if $G$ is triangle-free, or if G is bipartite, as well as computing the determinant of a distributed matrix.
Cite as

Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, and Ronald de Wolf. New bounds on the classical and quantum communication complexity of some graph properties. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 148-159, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{ivanyos_et_al:LIPIcs.FSTTCS.2012.148,
  author =	{Ivanyos, G\'{a}bor and Klauck, Hartmut and Lee, Troy and Santha, Miklos and de Wolf, Ronald},
  title =	{{New bounds on the classical and quantum communication complexity of some graph properties}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{148--159},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.148},
  URN =		{urn:nbn:de:0030-drops-38523},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.148},
  annote =	{Keywords: Graph properties, communication complexity, quantum communication}
}
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