BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Giannicola Scarpa

Giannicola Scarpa appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phmath.COComputation and Language

Catalog footprint

What is connected

11works
3topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2022arXiv

A gentle introduction to Quantum Natural Language Processing

The main goal of this master's thesis is to introduce Quantum Natural Language Processing (QNLP) in a way understandable by both the NLP engineer and the quantum computing practitioner. QNLP is a recent application of quantum computing that aims at representing sentences' meaning as vectors encoded into quantum computers. To achieve this, the distributional meaning of words is extended by the compositional meaning of sentences (DisCoCat model) : the vectors representing words' meanings are composed through the syntactic structure of the sentence. This is done using an algorithm based on tensor products. We see that this algorithm is inefficient on classical computers but scales well using quantum circuits. After exposing the practical details of its implementation, we go through three use-cases.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Near-Optimal and Explicit Bell Inequality Violations

Entangled quantum systems can exhibit correlations that cannot be simulated classically. For historical reasons such correlations are called "Bell inequality violations." We give two new two-player games with Bell inequality violations that are stronger, fully explicit, and arguably simpler than earlier work. The first game is based on the Hidden Matching problem of quantum communication complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with probability 1 by a strategy using a maximally entangled state with local dimension $n$ (e.g., $\log n$ EPR-pairs), while we show that the winning probability of any classical strategy differs from ${1}/{2}$ by at most $O((\log n)/\sqrt{n})$. The second game is based on the integrality gap for Unique Games by Khot and Vishnoi and the quantum rounding procedure of Kempe, Regev, and Toner. Here $n$-dimensional entanglement allows the game to be won with probability $1/(\log n)^2$, while the best winning probability without entanglement is $1/n$. This near-linear ratio is almost optimal, both in terms of the local dimension of the entangled state, and in terms of the number of possible outputs of the two players.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Entanglement-assisted zero-error source-channel coding

We study the use of quantum entanglement in the zero-error source-channel coding problem. Here, Alice and Bob are connected by a noisy classical one-way channel, and are given correlated inputs from a random source. Their goal is for Bob to learn Alice's input while using the channel as little as possible. In the zero-error regime, the optimal rates of source codes and channel codes are given by graph parameters known as the Witsenhausen rate and Shannon capacity, respectively. The Lovász theta number, a graph parameter defined by a semidefinite program, gives the best efficiently-computable upper bound on the Shannon capacity and it also upper bounds its entanglement-assisted counterpart. At the same time it was recently shown that the Shannon capacity can be increased if Alice and Bob may use entanglement. Here we partially extend these results to the source-coding problem and to the more general source-channel coding problem. We prove a lower bound on the rate of entanglement-assisted source-codes in terms Szegedy's number (a strengthening of the theta number). This result implies that the theta number lower bounds the entangled variant of the Witsenhausen rate. We also show that entanglement can allow for an unbounded improvement of the asymptotic rate of both classical source codes and classical source-channel codes. Our separation results use low-degree polynomials due to Barrington, Beigel and Rudich, Hadamard matrices due to Xia and Liu and a new application of remote state preparation.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Graph-theoretical Bounds on the Entangled Value of Non-local Games

We introduce a novel technique to give bounds to the entangled value of non-local games. The technique is based on a class of graphs used by Cabello, Severini and Winter in 2010. The upper bound uses the famous Lovász theta number and is efficiently computable; the lower one is based on the quantum independence number, which is a quantity used in the study of entanglement-assisted channel capacities and graph homomorphism games.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Parallel Repetition of Free Entangled Games: Simplification and Improvements

In a two-player game, two cooperating but non communicating players, Alice and Bob, receive inputs taken from a probability distribution. Each of them produces an output and they win the game if they satisfy some predicate on their inputs/outputs. The entangled value $ω^*(G)$ of a game $G$ is the maximum probability that Alice and Bob can win the game if they are allowed to share an entangled state prior to receiving their inputs. The $n$-fold parallel repetition $G^n$ of $G$ consists of $n$ instances of $G$ where Alice and Bob receive all the inputs at the same time and must produce all the outputs at the same time. They win $G^n$ if they win each instance of $G$. Recently, there has been a series of works showing parallel repetition with exponential decay for projection games [DSV13], games on the uniform distribution [CS14] and for free games, i.e. games on a product distribution [JPY13]. This article is meant to be a follow up of [CS14], where we improve and simplify several parts of our previous paper. Our main result is that for any free game $G$ with value $ω^*(G)=1-\varepsilon$, we have $ω^*(G^n) \le (1 - \varepsilon^2)^{Ω(\frac{n}{\log(l)})}$ where $l$ is the size of the output set of the game. This result improves on both the results in [JPY13] and [CS14]. The framework we use can also be extended to free projection games. We show that for a free projection game $G$ with value $ω^*(G)=1-\varepsilon$, we have $ω^*(G^n) \le (1 - \varepsilon)^{Ω(n)}$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Multi-party zero-error classical channel coding with entanglement

We study the effects of quantum entanglement on the performance of two classical zero-error communication tasks among multiple parties. Both tasks are generalizations of the two-party zero-error channel-coding problem, where a sender and a receiver want to perfectly communicate messages through a one-way classical noisy channel. If the two parties are allowed to share entanglement, there are several positive results that show the existence of channels for which they can communicate strictly more than what they could do with classical resources. In the first task, one sender wants to communicate a common message to multiple receivers. We show that if the number of receivers is greater than a certain threshold then entanglement does not allow for an improvement in the communication for any finite number of uses of the channel. On the other hand, when the number of receivers is fixed, we exhibit a class of channels for which entanglement gives an advantage. The second problem we consider features multiple collaborating senders and one receiver. Classically, cooperation among the senders might allow them to communicate on average more messages than the sum of their individual possibilities. We show that whenever a channel allows single-sender entanglement-assisted advantage, then the gain extends also to the multi-sender case. Furthermore, we show that entanglement allows for a peculiar amplification of information which cannot happen classically, for a fixed number of uses of a channel with multiple senders.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost

In a two-player game, two cooperating but non communicating players, Alice and Bob, receive inputs taken from a probability distribution. Each of them produces an output and they win the game if they satisfy some predicate on their inputs/outputs. The entangled value $ω^*(G)$ of a game $G$ is the maximum probability that Alice and Bob can win the game if they are allowed to share an entangled state prior to receiving their inputs. The $n$-fold parallel repetition $G^n$ of $G$ consists of $n$ instances of $G$ where the players receive all the inputs at the same time and produce all the outputs at the same time. They win $G^n$ if they win each instance of $G$. In this paper we show that for any game $G$ such that $ω^*(G) = 1 - \varepsilon < 1$, $ω^*(G^n)$ decreases exponentially in $n$. First, for any game $G$ on the uniform distribution, we show that $ω^*(G^n) = (1 - \varepsilon^2)^{Ω\left(\frac{n}{\log(|I||O|)} - |\log(\varepsilon)|\right)}$, where $|I|$ and $|O|$ are the sizes of the input and output sets. From this result, we show that for any entangled game $G$, $ω^*(G^n) \le (1 - \varepsilon^2)^{Ω(\frac{n}{Q\log(|I||O|)} - \frac{|\log(\varepsilon)|}{Q})}$ where $p$ is the input distribution of $G$ and $Q= \frac{|I|^2 \max_{xy} p_{xy}^2 }{\min_{xy} p_{xy} }$. This implies parallel repetition with exponential decay as long as $\min_{xy} \{p_{xy}\} \neq 0$ for general games. To prove this parallel repetition, we introduce the concept of \emph{Superposed Information Cost} for entangled games which is inspired from the information cost used in communication complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Exclusivity structures and graph representatives of local complementation orbits

We describe a construction that maps any connected graph G on three or more vertices into a larger graph, H(G), whose independence number is strictly smaller than its Lovász number which is equal to its fractional packing number. The vertices of H(G) represent all possible events consistent with the stabilizer group of the graph state associated with G, and exclusive events are adjacent. Mathematically, the graph H(G) corresponds to the orbit of G under local complementation. Physically, the construction translates into graph-theoretic terms the connection between a graph state and a Bell inequality maximally violated by quantum mechanics. In the context of zero-error information theory, the construction suggests a protocol achieving the maximum rate of entanglement-assisted capacity, a quantum mechanical analogue of the Shannon capacity, for each H(G). The violation of the Bell inequality is expressed by the one-shot version of this capacity being strictly larger than the independence number. Finally, given the correspondence between graphs and exclusivity structures, we are able to compute the independence number for certain infinite families of graphs with the use of quantum non-locality, therefore highlighting an application of quantum theory in the proof of a purely combinatorial statement.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Generalization of Kochen-Specker Sets Relates Quantum Coloring to Entanglement-Assisted Channel Capacity

We introduce two generalizations of Kochen-Specker (KS) sets: projective KS sets and generalized KS sets. We then use projective KS sets to characterize all graphs for which the chromatic number is strictly larger than the quantum chromatic number. Here, the quantum chromatic number is defined via a nonlocal game based on graph coloring. We further show that from any graph with separation between these two quantities, one can construct a classical channel for which entanglement assistance increases the one-shot zero-error capacity. As an example, we exhibit a new family of classical channels with an exponential increase.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number

The quantum chromatic number of a graph $G$ is sandwiched between its chromatic number and its clique number, which are well known NP-hard quantities. We restrict our attention to the rank-1 quantum chromatic number $χ_q^{(1)}(G)$, which upper bounds the quantum chromatic number, but is defined under stronger constraints. We study its relation with the chromatic number $χ(G)$ and the minimum dimension of orthogonal representations $ξ(G)$. It is known that $ξ(G) \leq χ_q^{(1)}(G) \leq χ(G)$. We answer three open questions about these relations: we give a necessary and sufficient condition to have $ξ(G) = χ_q^{(1)}(G)$, we exhibit a class of graphs such that $ξ(G) < χ_q^{(1)}(G)$, and we give a necessary and sufficient condition to have $χ_q^{(1)}(G) < χ(G)$. Our main tools are Kochen-Specker sets, collections of vectors with a traditionally important role in the study of noncontextuality of physical theories, and more recently in the quantification of quantum zero-error capacities. Finally, as a corollary of our results and a result by Avis, Hasegawa, Kikuchi, and Sasaki on the quantum chromatic number, we give a family of Kochen-Specker sets of growing dimension.

0 citations0 reviewsNo code linkedOpen access