Document

**Published in:** LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

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.

Iordanis Kerenidis and Anupam Prakash. Quantum Recommendation Systems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 49:1-49:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kerenidis_et_al:LIPIcs.ITCS.2017.49, author = {Kerenidis, Iordanis and Prakash, Anupam}, title = {{Quantum Recommendation Systems}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {49:1--49:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.49}, URN = {urn:nbn:de:0030-drops-81541}, doi = {10.4230/LIPIcs.ITCS.2017.49}, annote = {Keywords: Recommendation systems, quantum machine learning, singular value estimation, matrix sampling, quantum algorithms.} }

Document

**Published in:** LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

We define the Streaming Communication model that combines the main aspects of communication complexity and streaming. Input arrives as a stream, spread between several agents across a network. Each agent has a bounded memory, which can be updated upon receiving a new bit, or a message from another agent. We provide tight tradeoffs between the necessary resources, i.e. communication between agents 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.

Lucas Boczkowski, Iordanis Kerenidis, and Frédéric Magniez. Streaming Communication Protocols. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 130:1-130:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{boczkowski_et_al:LIPIcs.ICALP.2017.130, author = {Boczkowski, Lucas and Kerenidis, Iordanis and Magniez, Fr\'{e}d\'{e}ric}, title = {{Streaming Communication Protocols}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {130:1--130:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.130}, URN = {urn:nbn:de:0030-drops-74404}, doi = {10.4230/LIPIcs.ICALP.2017.130}, annote = {Keywords: Networks, Communication Complexity, Streaming Algorithms} }

Document

**Published in:** LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

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. Our new conjecture is weaker than the original QPCP conjecture and hence provides a natural intermediate step towards proving the quantum PCP theorem. Furthermore, this is the first equivalence between a quantum PCP statement and the inapproximability of quantum multi-prover games.

Alex B. Grilo, Iordanis Kerenidis, and Attila Pereszlényi. Pointer Quantum PCPs and Multi-Prover Games. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{grilo_et_al:LIPIcs.MFCS.2016.21, author = {Grilo, Alex B. and Kerenidis, Iordanis and Pereszl\'{e}nyi, Attila}, title = {{Pointer Quantum PCPs and Multi-Prover Games}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {21:1--21:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.21}, URN = {urn:nbn:de:0030-drops-64364}, doi = {10.4230/LIPIcs.MFCS.2016.21}, annote = {Keywords: computational complexity, quantum computation, PCP theorem} }

Document

**Published in:** LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

We introduce the new measure of Public Information Complexity (PIC), as a tool for the study of multi-party computation protocols, and of quantities such as their communication complexity, or the amount of randomness they require in the context of information-theoretic private computations. We are able to use this measure directly in the natural asynchronous message-passing peer-to-peer model and show a number of interesting properties and applications of our new notion:
the Public Information Complexity is a lower bound on the Communication Complexity and an upper bound on the Information Complexity; the difference between the Public Information Complexity and the Information Complexity provides a lower bound on the amount of randomness used in a protocol; any communication protocol can be compressed to its Public Information Cost; an explicit calculation of the zero-error Public Information Complexity of the k-party, n-bit Parity function, where a player outputs the bit-wise parity of the inputs. The latter result establishes that the amount of randomness needed for a private protocol that computes this function is Omega(n).

Iordanis Kerenidis, Adi Rosén, and Florent Urrutia. Multi-Party Protocols, Information Complexity and Privacy. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kerenidis_et_al:LIPIcs.MFCS.2016.57, author = {Kerenidis, Iordanis and Ros\'{e}n, Adi and Urrutia, Florent}, title = {{Multi-Party Protocols, Information Complexity and Privacy}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {57:1--57:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.57}, URN = {urn:nbn:de:0030-drops-64696}, doi = {10.4230/LIPIcs.MFCS.2016.57}, annote = {Keywords: multi-party protocols, information theory, communication complexity, multi-party private computation (MPC), randomness} }

Document

**Published in:** LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

We propose an information theoretically secure secret-key quantum money scheme in which the verification of a coin is classical and consists of only one round; namely, a classical query from the user to the bank and an accept/reject answer from the bank to the user. A coin can be verified polynomially (on the number of its qubits) many times before it expires. Our scheme is an improvement on Gavinsky's scheme [Gavinsky, Computational Complexity, 2012], where three rounds of interaction are needed and is based on the notion of quantum retrieval games. Moreover, we propose a public-key quantum money scheme which uses one-time memories as a building block and is computationally secure in the random oracle model. This construction is derived naturally from our secret-key scheme using the fact that one-time memories are a special case of quantum retrieval games.

Marios Georgiou and Iordanis Kerenidis. New Constructions for Quantum Money. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 92-110, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{georgiou_et_al:LIPIcs.TQC.2015.92, author = {Georgiou, Marios and Kerenidis, Iordanis}, title = {{New Constructions for Quantum Money}}, booktitle = {10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)}, pages = {92--110}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-96-5}, ISSN = {1868-8969}, year = {2015}, volume = {44}, editor = {Beigi, Salman and K\"{o}nig, Robert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.92}, URN = {urn:nbn:de:0030-drops-55510}, doi = {10.4230/LIPIcs.TQC.2015.92}, annote = {Keywords: Quantum Money, Quantum Cryptography, Quantum Retrieval Games} }

Document

**Published in:** LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)

Random Access Codes 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 rho_x, such that Bob, when receiving the state rho_x, can choose any bit i in [n] and recover the input bit x_i with high probability. Here we study a variant called parity-oblivious random acres 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 form the single bits x_i.
We provide the optimal quantum parity-oblivious random access codes and show that they are asymptotically better than the optimal classical ones. For this, we relate such encodings to a non-local game and provide tight bounds for the success probability of the non-local game via semi-definite programming. Our results provide a large non-contextuality inequality violation and resolve the main open question in [Spekkens et al., Phys. Review Letters, 2009].

André Chailloux, Iordanis Kerenidis, Srijita Kundu, and Jamie Sikora. Optimal Bounds for Parity-Oblivious Random Access Codes with Applications. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 76-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{chailloux_et_al:LIPIcs.TQC.2014.76, author = {Chailloux, Andr\'{e} and Kerenidis, Iordanis and Kundu, Srijita and Sikora, Jamie}, title = {{Optimal Bounds for Parity-Oblivious Random Access Codes with Applications}}, booktitle = {9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)}, pages = {76--87}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-73-6}, ISSN = {1868-8969}, year = {2014}, volume = {27}, editor = {Flammia, Steven T. and Harrow, Aram W.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.76}, URN = {urn:nbn:de:0030-drops-48084}, doi = {10.4230/LIPIcs.TQC.2014.76}, annote = {Keywords: quantum information theory, contextuality, semidefinite programming} }

Document

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

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.

André Chailloux, Iordanis Kerenidis, and Jamie Sikora. Lower bounds for Quantum Oblivious Transfer. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 157-168, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{chailloux_et_al:LIPIcs.FSTTCS.2010.157, author = {Chailloux, Andr\'{e} and Kerenidis, Iordanis and Sikora, Jamie}, title = {{Lower bounds for Quantum Oblivious Transfer}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}, pages = {157--168}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-23-1}, ISSN = {1868-8969}, year = {2010}, volume = {8}, editor = {Lodaya, Kamal and Mahajan, Meena}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.157}, URN = {urn:nbn:de:0030-drops-28613}, doi = {10.4230/LIPIcs.FSTTCS.2010.157}, annote = {Keywords: quantum oblivious transfer, coin flipping protocol, semidefinite programming} }

Document

**Published in:** LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

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 $a \oplus b = x \wedge y$. 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 show that non-local box complexity has interesting applications to classical cryptography, in particular to secure function evaluation, and study the question posed by Beimel and Malkin \cite{BM} 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 \nlbs, while
no finite bound was previously known.

Marc Kaplan, Iordanis Kerenidis, Sophie Laplante, and Jérémie Roland. Non-Local Box Complexity and Secure Function Evaluation. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 239-250, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{kaplan_et_al:LIPIcs.FSTTCS.2009.2322, author = {Kaplan, Marc and Kerenidis, Iordanis and Laplante, Sophie and Roland, J\'{e}r\'{e}mie}, title = {{Non-Local Box Complexity and Secure Function Evaluation}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {239--250}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2322}, URN = {urn:nbn:de:0030-drops-23226}, doi = {10.4230/LIPIcs.FSTTCS.2009.2322}, annote = {Keywords: Communication complexity, non-locality, non-local boxes, secure function evaluation} }

Document

**Published in:** LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

In quantum zero knowledge, the assumption was made that the
verifier is only using unitary operations. Under this assumption,
many nice properties have been shown about quantum zero
knowledge, including the fact that Honest-Verifier Quantum
Statistical Zero Knowledge ($HVQSZK$) is equal to
Cheating-Verifier Quantum Statistical Zero Knowledge ($QSZK$)
(see ~\cite{Wat02,Wat06}).
In this paper, we study what happens when we allow an honest
verifier to flip some coins in addition to using unitary
operations. Flipping a coin is a non-unitary operation but
doesn\'t seem at first to enhance the cheating possibilities of
the verifier since a classical honest verifier can flip coins. In
this setting, we show an unexpected result: any classical
Interactive Proof has an Honest-Verifier Quantum Statistical Zero
Knowledge proof with coins. Note that in the classical case,
honest verifier $SZK$ is no more powerful than $SZK$ and hence it
is not believed to contain even $NP$. On the other hand, in the
case of cheating verifiers, we show that Quantum Statistical Zero
Knowledge where the verifier applies any non-unitary operation is
equal to Quantum Zero-Knowledge where the verifier uses only
unitaries.
One can think of our results in two complementary ways. If we
would like to use the honest verifier model as a means to study
the general model by taking advantage of their equivalence, then
it is imperative to use the unitary definition without coins,
since with the general one this equivalence is most probably not
true. On the other hand, if we would like to use quantum zero
knowledge protocols in a cryptographic scenario where the
honest-but-curious model is sufficient, then adding the unitary
constraint severely decreases the power of quantum zero knowledge
protocols.

Andre Chailloux and Iordanis Kerenidis. Increasing the power of the verifier in Quantum Zero Knowledge. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 95-106, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{chailloux_et_al:LIPIcs.FSTTCS.2008.1744, author = {Chailloux, Andre and Kerenidis, Iordanis}, title = {{Increasing the power of the verifier in Quantum Zero Knowledge}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {95--106}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-08-8}, ISSN = {1868-8969}, year = {2008}, volume = {2}, editor = {Hariharan, Ramesh and Mukund, Madhavan and Vinay, V}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1744}, URN = {urn:nbn:de:0030-drops-17446}, doi = {10.4230/LIPIcs.FSTTCS.2008.1744}, annote = {Keywords: Quantum cryptography, zero-knowledge protocols, honest-verifier, quantum semi-honest model, hiddenquantum cryptography, zero-knowledge protocols, honest-verifier, quantum semi-honest model, hidden-bits} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail