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

Iordanis Kerenidis

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

ResearcherUnclaimed source record
quant-phComputational ComplexityData Structures and AlgorithmsComputer Science and Game TheoryCryptography and SecurityInformation RetrievalMachine LearningNetworking and Internet Architecture

Catalog footprint

What is connected

29works
8topics
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

29 published item(s)

preprint2022arXiv

Low depth algorithms for quantum amplitude estimation

We design and analyze two new low depth algorithms for amplitude estimation (AE) achieving an optimal tradeoff between the quantum speedup and circuit depth. For $β\in (0,1]$, our algorithms require $N= \tilde{O}( \frac{1}{ ε^{1+β}})$ oracle calls and require the oracle to be called sequentially $D= O( \frac{1}{ ε^{1-β}})$ times to perform amplitude estimation within additive error $ε$. These algorithms interpolate between the classical algorithm $(β=1)$ and the standard quantum algorithm ($β=0$) and achieve a tradeoff $ND= O(1/ε^{2})$. These algorithms bring quantum speedups for Monte Carlo methods closer to realization, as they can provide speedups with shallower circuits. The first algorithm (Power law AE) uses power law schedules in the framework introduced by Suzuki et al \cite{S20}. The algorithm works for $β\in (0,1]$ and has provable correctness guarantees when the log-likelihood function satisfies regularity conditions required for the Bernstein Von-Mises theorem. The second algorithm (QoPrime AE) uses the Chinese remainder theorem for combining lower depth estimates to achieve higher accuracy. The algorithm works for discrete $β=q/k$ where $k \geq 2$ is the number of distinct coprime moduli used by the algorithm and $1 \leq q \leq k-1$, and has a fully rigorous correctness proof. We analyze both algorithms in the presence of depolarizing noise and provide numerical comparisons with the state of the art amplitude estimation algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Quantum machine learning with subspace states

We introduce a new approach for quantum linear algebra based on quantum subspace states and present three new quantum machine learning algorithms. The first is a quantum determinant sampling algorithm that samples from the distribution $\Pr[S]= det(X_{S}X_{S}^{T})$ for $|S|=d$ using $O(nd)$ gates and with circuit depth $O(d\log n)$. The state of art classical algorithm for the task requires $O(d^{3})$ operations \cite{derezinski2019minimax}. The second is a quantum singular value estimation algorithm for compound matrices $\mathcal{A}^{k}$, the speedup for this algorithm is potentially exponential. It decomposes a $\binom{n}{k}$ dimensional vector of order-$k$ correlations into a linear combination of subspace states corresponding to $k$-tuples of singular vectors of $A$. The third algorithm reduces exponentially the depth of circuits used in quantum topological data analysis from $O(n)$ to $O(\log n)$. Our basic tool are quantum subspace states, defined as $|Col(X)\rangle = \sum_{S\subset [n], |S|=d} det(X_{S}) |S\rangle$ for matrices $X \in \mathbb{R}^{n \times d}$ such that $X^{T} X = I_{d}$, that encode $d$-dimensional subspaces of $\mathbb{R}^{n}$. We develop two efficient state preparation techniques, the first using Givens circuits uses the representation of a subspace as a sequence of Givens rotations, while the second uses efficient implementations of unitaries $Γ(x) = \sum_{i} x_{i} Z^{\otimes (i-1)} \otimes X \otimes I^{n-i}$ with $O(\log n)$ depth circuits that we term Clifford loaders.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Experimental demonstration of quantum advantage for NP verification with limited information

In recent years, many computational tasks have been proposed as candidates for showing a quantum computational advantage, that is an advantage in the time needed to perform the task using a quantum instead of a classical machine. Nevertheless, practical demonstrations of such an advantage remain particularly challenging because of the difficulty in bringing together all necessary theoretical and experimental ingredients. Here, we show an experimental demonstration of a quantum computational advantage in a prover-verifier interactive setting, where the computational task consists in the verification of an NP-complete problem by a verifier who only gets limited information about the proof sent by an untrusted prover in the form of a series of unentangled quantum states. We provide a simple linear optical implementation that can perform this verification task efficiently (within a few seconds), while we also provide strong evidence that, fixing the size of the proof, a classical computer would take much longer time (assuming only that it takes exponential time to solve an NP-complete problem). While our computational advantage concerns a specific task in a scenario of mostly theoretical interest, it brings us a step closer to potential useful applications, such as server-client quantum computing.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Quantum gradient descent for linear systems and least squares

Quantum machine learning and optimization are exciting new areas that have been brought forward by the breakthrough quantum algorithm of Harrow, Hassidim and Lloyd for solving systems of linear equations. The utility of {classical} linear system solvers extends beyond linear algebra as they can be leveraged to solve optimization problems using iterative methods like gradient descent. In this work, we provide the first quantum method for performing gradient descent when the gradient is an affine function. Performing $τ$ steps of the gradient descent requires time $O(τC_S)$ for weighted least squares problems, where $C_S$ is the cost of performing one step of the gradient descent quantumly, which at times can be considerably smaller than the classical cost. We illustrate our method by providing two applications: first, for solving positive semidefinite linear systems, and, second, for performing stochastic gradient descent for the weighted least squares problem with reduced quantum memory requirements. We also provide a quantum linear system solver in the QRAM data structure model that provides significant savings in cost for large families of matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Quantum Expectation-Maximization for Gaussian Mixture Models

The Expectation-Maximization (EM) algorithm is a fundamental tool in unsupervised machine learning. It is often used as an efficient way to solve Maximum Likelihood (ML) estimation problems, especially for models with latent variables. It is also the algorithm of choice to fit mixture models: generative models that represent unlabelled points originating from $k$ different processes, as samples from $k$ multivariate distributions. In this work we define and use a quantum version of EM to fit a Gaussian Mixture Model. Given quantum access to a dataset of $n$ vectors of dimension $d$, our algorithm has convergence and precision guarantees similar to the classical algorithm, but the runtime is only polylogarithmic in the number of elements in the training set, and is polynomial in other parameters - as the dimension of the feature space, and the number of components in the mixture. We generalize further the algorithm in two directions. First, we show how to fit any mixture model of probability distributions in the exponential family. Then, we show how to use this algorithm to compute the Maximum a Posteriori (MAP) estimate of a mixture model: the Bayesian approach to likelihood estimation problems. We discuss the performance of the algorithm on a dataset that is expected to be classified successfully by this algorithm, arguing that on those cases we can give strong guarantees on the runtime.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Quantum weak coin flipping with a single photon

Weak coin flipping is among the fundamental cryptographic primitives which ensure the security of modern communication networks. It allows two mistrustful parties to remotely agree on a random bit when they favor opposite outcomes. Unlike other two-party computations, one can achieve information-theoretic security using quantum mechanics only: both parties are prevented from biasing the flip with probability higher than $1/2+ε$, where $ε$ is arbitrarily low. Classically, the dishonest party can always cheat with probability $1$ unless computational assumptions are used. Despite its importance, no physical implementation has been proposed for quantum weak coin flipping. Here, we present a practical protocol that requires a single photon and linear optics only. We show that it is fair and balanced even when threshold single-photon detectors are used, and reaches a bias as low as $ε=1/\sqrt{2}-1/2\approx 0.207$. We further show that the protocol may display quantum advantage over a few hundred meters with state-of-the-art technology.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal bounds for parity-oblivious random access codes

Random access coding is an information task that has been extensively studied and found many applications in quantum information. In this scenario, Alice receives an $n$-bit string $x$, and wishes to encode $x$ into a quantum state $ρ_x$, such that Bob, when receiving the state $ρ_x$, can choose any bit $i \in [n]$ and recover the input bit $x_i$ with high probability. Here we study two variants: parity-oblivious random access codes, where we impose the cryptographic property that Bob cannot infer any information about the parity of any subset of bits of the input apart from the single bits $x_i$; and even-parity-oblivious random access codes, where Bob cannot infer any information about the parity of any even-size subset of bits of the input. In this paper, we provide the optimal bounds for parity-oblivious quantum random access codes and show that they are asymptotically better than the optimal classical ones. Our results provide a large non-contextuality inequality violation and resolve the main open problem in a work of Spekkens, Buzacott, Keehn, Toner, and Pryde (2009). Second, we provide the optimal bounds for even-parity-oblivious random access codes by proving their equivalence to a non-local game and by providing tight bounds for the success probability of the non-local game via semidefinite programming. In the case of even-parity-oblivious random access codes, the cryptographic property holds also in the device-independent model.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Pointer Quantum PCPs and Multi-Prover Games

The quantum PCP (QPCP) conjecture states that all problems in QMA, the quantum analogue of NP, admit quantum verifiers that only act on a constant number of qubits of a polynomial size quantum proof and have a constant gap between completeness and soundness. Despite an impressive body of work trying to prove or disprove the quantum PCP conjecture, it still remains widely open. The above-mentioned proof verification statement has also been shown equivalent to the QMA-completeness of the Local Hamiltonian problem with constant relative gap. Nevertheless, unlike in the classical case, no equivalent formulation in the language of multi-prover games is known. In this work, we propose a new type of quantum proof systems, the Pointer QPCP, where a verifier first accesses a classical proof that he can use as a pointer to which qubits from the quantum part of the proof to access. We define the Pointer QPCP conjecture, that states that all problems in QMA admit quantum verifiers that first access a logarithmic number of bits from the classical part of a polynomial size proof, then act on a constant number of qubits from the quantum part of the proof, and have a constant gap between completeness and soundness. We define a new QMA-complete problem, the Set Local Hamiltonian problem, and a new restricted class of quantum multi-prover games, called CRESP games. We use them to provide two other equivalent statements to the Pointer QPCP conjecture: the Set Local Hamiltonian problem with constant relative gap is QMA-complete; and the approximation of the maximum acceptance probability of CRESP games up to a constant additive factor is as hard as QMA. This is the first equivalence between a quantum PCP statement and the inapproximability of quantum multi-prover games.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

QMA with subset state witnesses

The class QMA plays a fundamental role in quantum complexity theory and it has found surprising connections to condensed matter physics and in particular in the study of the minimum energy of quantum systems. In this paper, we further investigate the class QMA and its related class QCMA by asking what makes quantum witnesses potentially more powerful than classical ones. We provide a definition of a new class, SQMA, where we restrict the possible quantum witnesses to the "simpler" subset states, i.e. a uniform superposition over the elements of a subset of n-bit strings. Surprisingly, we prove that this class is equal to QMA, hence providing a new characterisation of the class QMA. We also prove the analogous result for QMA(2) and describe a new complete problem for QMA and a stronger lower bound for the class QMA$_1$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Quantum Recommendation Systems

A recommendation system uses the past purchases or ratings of $n$ products by a group of $m$ users, in order to provide personalized recommendations to individual users. The information is modeled as an $m \times n$ preference matrix which is assumed to have a good rank-$k$ approximation, for a small constant $k$. In this work, we present a quantum algorithm for recommendation systems that has running time $O(\text{poly}(k)\text{polylog}(mn))$. All known classical algorithms for recommendation systems that work through reconstructing an approximation of the preference matrix run in time polynomial in the matrix dimension. Our algorithm provides good recommendations by sampling efficiently from an approximation of the preference matrix, without reconstructing the entire matrix. For this, we design an efficient quantum procedure to project a given vector onto the row space of a given matrix. This is the first algorithm for recommendation systems that runs in time polylogarithmic in the dimensions of the matrix and provides an example of a quantum machine learning algorithm for a real world application.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Shortcuts to quantum network routing

A quantum network promises to enable long distance quantum communication, and assemble small quantum devices into a large quantum computing cluster. Each network node can thereby be seen as a small few qubit quantum computer. Qubits can be sent over direct physical links connecting nearby quantum nodes, or by means of teleportation over pre-established entanglement amongst distant network nodes. Such pre-shared entanglement effectively forms a shortcut - a virtual quantum link - which can be used exactly once. Here, we present an abstraction of a quantum network that allows ideas from computer science to be applied to the problem of routing qubits, and manage entanglement in the network. Specifically, we consider a scenario in which each quantum network node can create EPR pairs with its immediate neighbours over a physical connection, and perform entanglement swapping operations in order to create long distance virtual quantum links. We proceed to discuss the features unique to quantum networks, which call for the development of new routing techniques. As an example, we present two simple hierarchical routing schemes for a quantum network of N nodes for a ring and sphere topology. For these topologies we present efficient routing algorithms requiring O(log N) qubits to be stored at each network node, O(polylog N) time and space to perform routing decisions, and O(log N) timesteps to replenish the virtual quantum links in a model of entanglement generation.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Streaming Communication Protocols

We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. We consider two agents that want to compute some function that depends on inputs that are distributed to each agent. The inputs arrive as data streams and each agent has a bounded memory. Agents are allowed to communicate with each other and also update their memory based on the input bit they read and the previous message they received. We provide tight tradeoffs between the necessary resources, i.e. communication and memory, for some of the canonical problems from communication complexity by proving a strong general lower bound technique. Second, we analyze the Approximate Matching problem and show that the complexity of this problem (i.e. the achievable approximation ratio) in the one-way variant of our model is strictly different both from the streaming complexity and the one-way communication complexity thereof.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Nonlocality and conflicting interest games

Nonlocality enables two parties to win specific games with probabilities strictly higher than allowed by any classical theory. Nevertheless, all known such examples consider games where the two parties have a common interest, since they jointly win or lose the game. The main question we ask here is whether the nonlocal feature of quantum mechanics can offer an advantage in a scenario where the two parties have conflicting interests. We answer this in the affirmative by presenting a simple conflicting interest game, where quantum strategies outperform classical ones. Moreover, we show that our game has a fair quantum equilibrium with higher payoffs for both players than in any fair classical equilibrium. Finally, we play the game using a commercial entangled photon source and demonstrate experimentally the quantum advantage.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A simpler proof of existence of quantum weak coin flipping with arbitrarily small bias

Mochon's proof [Moc07] of existence of quantum weak coin flipping with arbitrarily small bias is a fundamental result in quantum cryptography, but at the same time one of the least understood. Though used several times as a black box in important follow-up results [Gan09, CK09, AS10, CK11, KZ13] the result has not been peer-reviewed, its novel techniques (and in particular Kitaev's point game formalism) have not been applied anywhere else, and an explicit protocol is missing. We believe that truly understanding the existence proof and the novel techniques it relies on would constitute a major step in quantum information theory, leading to deeper understanding of entanglement and of quantum protocols in general. In this work, we make a first step in this direction. We simplify parts of Mochon's construction considerably, making about 20 pages of analysis in the original proof superfluous, clarifying some other parts of the proof on the way, and presenting the proof in a way which is conceptually easier to grasp. We believe the resulting proof of existence is easier to understand, more readable, and certainly verifiable. Moreover, we analyze the resources needed to achieve a bias $ε$ and show that the number of qubits is $O(\log 1/ε)$, while the number of rounds is $(1/ε)^{O(1/ε)}$. A true understanding of the proof, including Kitaev's point game techniques and their applicability, as well as completing the task of constructing an explicit (and also simpler and more efficient) protocol, are left to future work.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Experimental plug&play quantum coin flipping

Performing complex cryptographic tasks will be an essential element in future quantum communication networks. These tasks are based on a handful of fundamental primitives, such as coin flipping, where two distrustful parties wish to agree on a randomly generated bit. Although it is known that quantum versions of these primitives can offer information-theoretic security advantages with respect to classical protocols, a demonstration of such an advantage in a practical communication scenario has remained elusive. Here, we experimentally implement a quantum coin flipping protocol that performs strictly better than classically possible over a distance suitable for communication over metropolitan area optical networks. The implementation is based on a practical plug&play system, designed for quantum key distribution. We also show how to combine our protocol with coin flipping protocols that are almost perfectly secure against bounded adversaries, hence enhancing them with a level of information-theoretic security. Our results offer a powerful toolbox for future secure quantum communications.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Reliable experimental quantification of bipartite entanglement without reference frames

Simply and reliably detecting and quantifying entanglement outside laboratory conditions will be essential for future quantum information technologies. Here we address this issue by proposing a method for generating expressions which can perform this task between two parties who do not share a common reference frame. These reference frame independent expressions only require simple local measurements, which allows us to experimentally test them using an off-the-shelf entangled photon source. We show that the values of these expressions provide bounds on the concurrence of the state, and demonstrate experimentally that these bounds are more reliable than values obtained from state tomography since characterizing experimental errors is easier in our setting. Furthermore, we apply this idea to other quantities, such as the Renyi and von Neumann entropies, which are also more reliably calculated directly from the raw data than from a tomographically reconstructed state. This highlights the relevance of our approach for practical quantum information applications that require entanglement.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Strong connections between quantum encodings, non-locality and quantum cryptography

Encoding information in quantum systems can offer surprising advantages but at the same time there are limitations that arise from the fact that measuring an observable may disturb the state of the quantum system. In our work, we provide an in-depth analysis of a simple question: What happens when we perform two measurements sequentially on the same quantum system? This question touches upon some fundamental properties of quantum mechanics, namely the uncertainty principle and the complementarity of quantum measurements. Our results have interesting consequences, for example they can provide a simple proof of the optimal quantum strategy in the famous Clauser-Horne-Shimony-Holt game. Moreover, we show that the way information is encoded in quantum systems can provide a different perspective in understanding other fundamental aspects of quantum information, like non-locality and quantum cryptography. We prove some strong equivalences between these notions and provide a number of applications in all areas.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Lower Bounds for Quantum Oblivious Transfer

Oblivious transfer is a fundamental primitive in cryptography. While perfect information theoretic security is impossible, quantum oblivious transfer protocols can limit the dishonest players' cheating. Finding the optimal security parameters in such protocols is an important open question. In this paper we show that every 1-out-of-2 oblivious transfer protocol allows a dishonest party to cheat with probability bounded below by a constant strictly larger than 1/2. Alice's cheating is defined as her probability of guessing Bob's index, and Bob's cheating is defined as his probability of guessing both input bits of Alice. In our proof, we relate these cheating probabilities to the cheating probabilities of a coin flipping protocol and conclude by using Kitaev's coin flipping lower bound. Then, we present an oblivious transfer protocol with two messages and cheating probabilities at most 3/4. Last, we extend Kitaev's semidefinite programming formulation to more general primitives, where the security is against a dishonest player trying to force the outcome of the other player, and prove optimal lower and upper bounds for them.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Lower bounds on information complexity via zero-communication protocols and applications

We show that almost all known lower bound methods for communication complexity are also lower bounds for the information complexity. In particular, we define a relaxed version of the partition bound of Jain and Klauck and prove that it lower bounds the information complexity of any function. Our relaxed partition bound subsumes all norm based methods (e.g. the factorization norm method) and rectangle-based methods (e.g. the rectangle/corruption bound, the smooth rectangle bound, and the discrepancy bound), except the partition bound. Our result uses a new connection between rectangles and zero-communication protocols where the players can either output a value or abort. We prove the following compression lemma: given a protocol for a function f with information complexity I, one can construct a zero-communication protocol that has non-abort probability at least 2^{-O(I)} and that computes f correctly with high probability conditioned on not aborting. Then, we show how such a zero-communication protocol relates to the relaxed partition bound. We use our main theorem to resolve three of the open questions raised by Braverman. First, we show that the information complexity of the Vector in Subspace Problem is Ω(n^{1/3}), which, in turn, implies that there exists an exponential separation between quantum communication complexity and classical information complexity. Moreover, we provide an Ω(n) lower bound on the information complexity of the Gap Hamming Distance Problem.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Multipartite entanglement verification resistant against dishonest parties

Future quantum information networks will likely consist of quantum and classical agents, who have the ability to communicate in a variety of ways with trusted and untrusted parties and securely delegate computational tasks to untrusted large-scale quantum computing servers. Multipartite quantum entanglement is a fundamental resource for such a network and hence it is imperative to study the possibility of verifying a multipartite entanglement source in a way that is efficient and provides strong guarantees even in the presence of multiple dishonest parties. In this work, we show how an agent of a quantum network can perform a distributed verification of a multipartite entangled source with minimal resources, which is, nevertheless, resistant against any number of dishonest parties. Moreover, we provide a tight tradeoff between the level of security and the distance between the state produced by the source and the ideal maximally entangled state. Last, by adding the resource of a trusted common random source, we can further provide security guarantees for all honest parties in the quantum network simultaneously.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A quantum protocol for sampling correlated equilibria unconditionally and without a mediator

A correlated equilibrium is a fundamental solution concept in game theory that enjoys many desirable properties. However, it requires a trusted mediator, which is a major drawback in many practical applications. A computational solution to this problem was proposed by Dodis, Halevi and Rabin. They extended the original game by adding an initial communication stage and showed that any correlated strategy for 2-player games can be achieved, provided that the players are computationally bounded. In this paper, we show that if the players can communicate via a quantum channel before the game, then any correlated equilibrium for 2-player games can be achieved, without a trusted mediator and unconditionally. This provides another example of a major advantage of quantum information processing. More precisely, we prove that for any correlated equilibrium p of a strategic game G, there exists an extended game (with a quantum communication initial stage) Q with an efficiently computable approximate Nash equilibrium q, such that the expected payoff for both players in q is at least as high as in p. The main cryptographic tool used in the construction is the quantum weak coin flipping protocol of Mochon.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the power of a unique quantum witness

In a celebrated paper, Valiant and Vazirani raised the question of whether the difficulty of NP-complete problems was due to the wide variation of the number of witnesses of their instances. They gave a strong negative answer by showing that distinguishing between instances having zero or one witnesses is as hard as recognizing NP, under randomized reductions. We consider the same question in the quantum setting and investigate the possibility of reducing quantum witnesses in the context of the complexity class QMA, the quantum analogue of NP. The natural way to quantify the number of quantum witnesses is the dimension of the witness subspace W in some appropriate Hilbert space H. We present an efficient deterministic procedure that reduces any problem where the dimension d of W is bounded by a polynomial to a problem with a unique quantum witness. The main idea of our reduction is to consider the Alternating subspace of the d-th tensor power of H. Indeed, the intersection of this subspace with the d-th tensor power of W is one-dimensional, and therefore can play the role of the unique quantum witness.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Optimal bounds for quantum bit commitment

Bit commitment is a fundamental cryptographic primitive with numerous applications. Quantum information allows for bit commitment schemes in the information theoretic setting where no dishonest party can perfectly cheat. The previously best-known quantum protocol by Ambainis achieved a cheating probability of at most 3/4[Amb01]. On the other hand, Kitaev showed that no quantum protocol can have cheating probability less than 1/sqrt{2} [Kit03] (his lower bound on coin flipping can be easily extended to bit commitment). Closing this gap has since been an important and open question. In this paper, we provide the optimal bound for quantum bit commitment. We first show a lower bound of approximately 0.739, improving Kitaev's lower bound. We then present an optimal quantum bit commitment protocol which has cheating probability arbitrarily close to 0.739. More precisely, we show how to use any weak coin flipping protocol with cheating probability 1/2 + eps in order to achieve a quantum bit commitment protocol with cheating probability 0.739 + O(eps). We then use the optimal quantum weak coin flipping protocol described by Mochon[Moc07]. To stress the fact that our protocol uses quantum effects beyond the weak coin flip, we show that any classical bit commitment protocol with access to perfect weak (or strong) coin flipping has cheating probability at least 3/4.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Practical Quantum Coin Flipping

In this article we show for the first time that quantum coin flipping with security guarantees that are strictly better than any classical protocol is possible to implement with current technology. Our protocol takes into account all aspects of an experimental implementation like losses, multi-photon pulses emitted by practical photon sources, channel noise, detector dark counts and finite quantum efficiency. We calculate the abort probability when both players are honest, as well as the probability of one player forcing his desired outcome. For channel length up to 21 km, we achieve a cheating probability that is better than in any classical protocol. Our protocol is easy to implement using attenuated laser pulses, with no need for entangled photons or any other specific resources.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Quantum Commitments from Complexity Assumptions

Bit commitment schemes are at the basis of modern cryptography. Since information-theoretic security is impossible both in the classical and the quantum regime, we need to look at computationally secure commitment schemes. In this paper, we study worst-case complexity assumptions that imply quantum bit-commitment schemes. First, we show that QSZK not included in QMA implies a computationally hiding and statistically binding auxiliary-input quantum commitment scheme. Additionally, we give auxiliary-input commitment schemes using quantum advice that depend on the much weaker assumption that QIP is not included in QMA (which is weaker than PSPACE not included in PP). Finally, we find a quantum oracle relative to which honest-verifier QSZK is not contained in QCMA, the class of languages that can be verified using a classical proof in quantum polynomial time.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Long distance two-party quantum cryptography made simple

Any two-party cryptographic primitive can be implemented using quantum communication under the assumption that it is difficult to store a large number of quantum states perfectly. However, achieving reliable quantum communication over long distances remains a difficult problem. Here, we consider a large network of nodes with only neighboring quantum links. We exploit properties of this cloud of nodes to enable any two nodes to achieve security even if they are not directly connected. Our results are based on techniques from classical cryptography and do not resort to technologically difficult procedures like entanglement swapping. More precisely, we show that oblivious transfer can be achieved in such a network if and only if there exists a path in the network between the sender and the receiver along which all nodes are honest. Finally, we show that useful notions of security can still be achieved when we relax the assumption of an honest path. For example, we show that we can combine our protocol for oblivious transfer with computational assumptions such that we obtain security if either there exists an honest path, or, as a backup, at least the adversary cannot solve a computational problem.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Non-Local Box Complexity and Secure Function Evaluation

A non-local box is an abstract device into which Alice and Bob input bits x and y respectively and receive outputs a and b respectively, where a, b are uniformly distributed and the parity of a+b equals xy. Such boxes have been central to the study of quantum or generalized non-locality as well as the simulation of non-signaling distributions. In this paper, we start by studying how many non-local boxes Alice and Bob need in order to compute a Boolean function f. We provide tight upper and lower bounds in terms of the communication complexity of the function both in the deterministic and randomized case. We then proceed to show that the study of non-local box complexity has interesting applications for classical computation as well. In particular, we look at secure function evaluation, and study the question posed by Beimel and Malkin of how many Oblivious Transfer calls Alice and Bob need in order to securely compute a function f. We show that this question is related to the non-local box complexity of the function and conclude by greatly improving their bounds. Finally, another consequence of our results is that traceless two-outcome measurements on maximally entangled states can be simulated with 3 non-local boxes, while no finite bound was previously known.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Exponential separations for one-way quantum communication complexity, with applications to cryptography

We give an exponential separation between one-way quantum and classical communication protocols for a partial Boolean function (a variant of the Boolean Hidden Matching Problem of Bar-Yossef et al.) Earlier such an exponential separation was known only for a relational problem. The communication problem corresponds to a \emph{strong extractor} that fails against a small amount of \emph{quantum} information about its random source. Our proof uses the Fourier coefficients inequality of Kahn, Kalai, and Linial. We also give a number of applications of this separation. In particular, we show that there are privacy amplification schemes that are secure against classical adversaries but not against quantum adversaries; and we give the first example of a key-expansion scheme in the model of bounded-storage cryptography that is secure against classical memory-bounded adversaries but not against quantum ones.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

On the Optimality of Quantum Encryption Schemes

It is well known that n bits of entropy are necessary and sufficient to perfectly encrypt n bits (one-time pad). Even if we allow the encryption to be approximate, the amount of entropy needed doesn't asymptotically change. However, this is not the case when we are encrypting quantum bits. For the perfect encryption of n quantum bits, 2n bits of entropy are necessary and sufficient (quantum one-time pad), but for approximate encryption one asymptotically needs only n bits of entropy. In this paper, we provide the optimal trade-off between the approximation measure epsilon and the amount of classical entropy used in the encryption of single quantum bits. Then, we consider n-qubit encryption schemes which are a composition of independent single-qubit ones and provide the optimal schemes both in the 2- and the operator-norm. Moreover, we provide a counterexample to show that the encryption scheme of Ambainis-Smith based on small-bias sets does not work in the operator-norm.

0 citations0 reviewsNo code linkedOpen access