Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

An introduction to quantum: computing, communication complexity protocols, nonlocality and graph parameters

Lucas Silva Arenstein

Published Dec 12, 2022• 0 citations
Publisher

Abstract

I'
DOI
10.11606/d.45.2022.tde-19062023-143615

Related papers

An Introduction to Quantum Computation and Quantum Communication

R. Pike

•Jan 1, 2000•6 citations

Nonlocality Distillation and Trivial Communication Complexity for High-Dimensional Systems

Yan Li, Xiang-Jun Ye, Jing‐Ling Chen

A nonlocality distillation protocol for arbitrary high-dimensional systems is proposed. We study the nonlocality distillation in the 2-input d-output bi-partite case. Firstly, we give the one-parameter nonlocal boxes and their correlated distilling protocol. Then, we generalize the one-parameter nonlocality distillation protocol to the two-parameter case. Furthermore, we introduce a contracting protocol testifying that the 2-input d-output nonlocal boxes make communication complexity trivial.

Chinese Physics Letters•Aug 1, 2016•5 citations

Quantum Advantage of Permutation-Invariant Functions in Communication Complexity

Yunqi Huang, Zekun Ye

We study how symmetry affects quantum advantage in two-party communication complexity. For any partial function $f$ on length-$n$ strings over a fixed alphabet of size $q$, invariant under simultaneous coordinate permutations, we prove $R^{\mathrm{pub}}(f)=O_q(t\log(2+n/t))$, where $t=\min\{n,Q^{\ast}(f)^2\}$, $R^{\mathrm{pub}}$ denotes public-coin randomized communication complexity, and $Q^{\ast}$ denotes entanglement-assisted quantum communication complexity. This bound is tight for set disjointness and extends the binary-alphabet result of Guan et al. with a smaller logarithmic overhead. The exponent of the logarithmic factor cannot be reduced by any fixed positive amount: for every fixed $\varepsilon\in(0,1)$, there are binary permutation-invariant partial functions with quantum communication complexity $O_\varepsilon(\log\log n)$ and randomized communication complexity $Ω_\varepsilon((\log n)^{1-\varepsilon})$. We also characterize quantum communication complexity by a combinatorial parameter up to a logarithmic factor. Growing alphabets and graph symmetries admit exponential separations. For every fixed $\varepsilon\in(0,1)$, we exhibit permutation-invariant partial functions on length-$n$ strings over an $n$-symbol alphabet with quantum communication complexity $O_\varepsilon(\log n)$ and randomized communication complexity $Ω_\varepsilon(n^{1-\varepsilon})$. For graph-invariant partial functions on $v$-vertex graphs, we obtain $O_\varepsilon(\log v)$ quantum versus $Ω_\varepsilon(v^{2-\varepsilon})$ randomized communication complexity. All separation protocols require no prior entanglement.

quant-pharXiv:2609.40116•Oct 1, 2026•0 citations

Uma introdução à computação quântica, protocolos de complexidade de comunicação quânticos, não-localidade e parâmetros quânticos de grafos

Lucas Silva Arenstein

What are the advantages quantum computing can provide when compared to classical computing? In this thesis, we aim to answer this question from different perspectives. To achieve this goal we divided this work into three parts. In Part I we start by studying the basic principles of quantum computing. Next, we introduce two quantum algorithms: the Deutsch-Jozsa and Grovers algorithms. The first algorithm has a lower query complexity and the second has a lower time complexity when compared with the best classical algorithm for the same problems. The final topic of this initial part is a detailed explanation and example of how to use Grovers algorithm to solve a Boolean formula in conjunctive normal form. In the second part, we focus on communication complexity problems. These problems are usually stated as follows: two spatially separated parties Alice and Bob receive an input from a referee. Their goal is to compute the value of a function that depends on both of their inputs with the least amount of communication between them. In Part II we will introduce protocols in which the transmission of quantum bits (qubits), instead of bits, can reduce the amount of communication necessary to solve these problems. We also study how Alice and Bob can use quantum entanglement to solve two communication complexity problems without communicating something that can not be done classically. In Part III we study nonlocal games inspired by standard graph theory parameters. A nonlocal game is usually defined as a game in which players that can share and do computations in an entangled state have some sort of advantage over classical players. We begin this final part by introducing the quantum chromatic number of a graph, which is the minimal number of colors necessary in a nonlocal game in which Alice and Bob can convince a referee with certainty that they have a proper coloring of the graph. We end this thesis by introducing other two quantum graph parameters, one related to graph homomorphism and the other to the independence number of a graph.

•Dec 12, 2022•0 citations

Quantum Computation: An Introduction for Engineers and Computer Scientists

Andreas de Vries

•Mar 1, 2012•5 citations

A Brief Introduction to Quantum Computing

Azar Khosravani, Constantin Rasinariu

The Physics Teacher•Dec 30, 2024•4 citations
We study how symmetry affects quantum advantage in two-party communication complexity. For any partial function fff on length-nnn strings over a fixed alphabet of size qqq, invariant under simultaneous coordinate permutations, we prove Rpub(f)=Oq(tlog⁡(2+n/t))R^{\mathrm{pub}}(f)=O_q(t\log(2+n/t))Rpub(f)=Oq​(tlog(2+n/t)), where t=min⁡{n,Q∗(f)2}t=\min\{n,Q^{\ast}(f)^2\}t=min{n,Q∗(f)2}, RpubR^{\mathrm{pub}}Rpub denotes public-coin randomized communication complexity, and Q∗Q^{\ast}Q∗ denotes entanglement-assisted quantum communication complexity. This bound is tight for set disjointness and extends the binary-alphabet result of Guan et al. with a smaller logarithmic overhead. The exponent of the logarithmic factor cannot be reduced by any fixed positive amount: for every fixed ε∈(0,1)\varepsilon\in(0,1)ε∈(0,1), there are binary permutation-invariant partial functions with quantum communication complexity Oε(log⁡log⁡n)O_\varepsilon(\log\log n)Oε​(loglogn) and randomized communication complexity Ωε((log⁡n)1−ε)Ω_\varepsilon((\log n)^{1-\varepsilon})Ωε​((logn)1−ε). We also characterize quantum communication complexity by a combinatorial parameter up to a logarithmic factor. Growing alphabets and graph symmetries admit exponential separations. For every fixed ε∈(0,1)\varepsilon\in(0,1)ε∈(0,1), we exhibit permutation-invariant partial functions on length-nnn strings over an nnn-symbol alphabet with quantum communication complexity Oε(log⁡n)O_\varepsilon(\log n)Oε​(logn) and randomized communication complexity Ωε(n1−ε)Ω_\varepsilon(n^{1-\varepsilon})Ωε​(n1−ε). For graph-invariant partial functions on vvv-vertex graphs, we obtain Oε(log⁡v)O_\varepsilon(\log v)Oε​(logv) quantum versus Ωε(v2−ε)Ω_\varepsilon(v^{2-\varepsilon})Ωε​(v2−ε) randomized communication complexity. All separation protocols require no prior entanglement.
What are the advantages quantum computing can provide when compared to classical computing? In this thesis, we aim to answer this question from different perspectives. To achieve this goal we divided this work into three parts. In Part I we start by studying the basic principles of quantum computing. Next, we introduce two quantum algorithms: the Deutsch-Jozsa and Grovers algorithms. The first algorithm has a lower query complexity and the second has a lower time complexity when compared with the best classical algorithm for the same problems. The final topic of this initial part is a detailed explanation and example of how to use Grovers algorithm to solve a Boolean formula in conjunctive normal form. In the second part, we focus on communication complexity problems. These problems are usually stated as follows: two spatially separated parties Alice and Bob receive an input from a referee. Their goal is to compute the value of a function that depends on both of their inputs with the least amount of communication between them. In Part II we will introduce protocols in which the transmission of quantum bits (qubits), instead of bits, can reduce the amount of communication necessary to solve these problems. We also study how Alice and Bob can use quantum entanglement to solve two communication complexity problems without communicating something that can not be done classically. In Part III we study nonlocal games inspired by standard graph theory parameters. A nonlocal game is usually defined as a game in which players that can share and do computations in an entangled state have some sort of advantage over classical players. We begin this final part by introducing the quantum chromatic number of a graph, which is the minimal number of colors necessary in a nonlocal game in which Alice and Bob can convince a referee with certainty that they have a proper coloring of the graph. We end this thesis by introducing other two quantum graph parameters, one related to graph homomorphism and the other to the independence number of a graph.