Search Results

Documents authored by Kashefi, Elham

Document
DOI: 10.4230/LIPIcs.TQC.2020.3
Building Trust for Continuous Variable Quantum States

Authors: Ulysse Chabaud, Tom Douce, Frédéric Grosshans, Elham Kashefi, and Damian Markham

Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)

Abstract
In this work we develop new methods for the characterisation of continuous variable quantum states using heterodyne measurement in both the trusted and untrusted settings. First, building on quantum state tomography with heterodyne detection, we introduce a reliable method for continuous variable quantum state certification, which directly yields the elements of the density matrix of the state considered with analytical confidence intervals. This method neither needs mathematical reconstruction of the data nor discrete binning of the sample space and uses a single Gaussian measurement setting. Second, beyond quantum state tomography and without its identical copies assumption, we promote our reliable tomography method to a general efficient protocol for verifying continuous variable pure quantum states with Gaussian measurements against fully malicious adversaries, i.e., making no assumptions whatsoever on the state generated by the adversary. These results are obtained using a new analytical estimator for the expected value of any operator acting on a continuous variable quantum state with bounded support over the Fock basis, computed with samples from heterodyne detection of the state.
Cite as

Ulysse Chabaud, Tom Douce, Frédéric Grosshans, Elham Kashefi, and Damian Markham. Building Trust for Continuous Variable Quantum States. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{chabaud_et_al:LIPIcs.TQC.2020.3,
  author =	{Chabaud, Ulysse and Douce, Tom and Grosshans, Fr\'{e}d\'{e}ric and Kashefi, Elham and Markham, Damian},
  title =	{{Building Trust for Continuous Variable Quantum States}},
  booktitle =	{15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-146-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{158},
  editor =	{Flammia, Steven T.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.3},
  URN =		{urn:nbn:de:0030-drops-120623},
  doi =		{10.4230/LIPIcs.TQC.2020.3},
  annote =	{Keywords: Continuous variable quantum information, reliable state tomography, certification, verification}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.6
Complexity-Theoretic Limitations on Blind Delegated Quantum Computation

Authors: Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, and Elham Kashefi

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Blind delegation protocols allow a client to delegate a computation to a server so that the server learns nothing about the input to the computation apart from its size. For the specific case of quantum computation we know, from work over the past decade, that blind delegation protocols can achieve information-theoretic security (provided the client and the server exchange some amount of quantum information). In this paper we prove, provided certain complexity-theoretic conjectures are true, that the power of information-theoretically secure blind delegation protocols for quantum computation (ITS-BQC protocols) is in a number of ways constrained. In the first part of our paper we provide some indication that ITS-BQC protocols for delegating polynomial-time quantum computations in which the client and the server interact only classically are unlikely to exist. We first show that having such a protocol in which the client and the server exchange O(n^d) bits of communication, implies that BQP subset MA/O(n^d). We conjecture that this containment is unlikely by proving that there exists an oracle relative to which BQP not subset MA/O(n^d). We then show that if an ITS-BQC protocol exists in which the client and the server interact only classically and which allows the client to delegate quantum sampling problems to the server (such as BosonSampling) then there exist non-uniform circuits of size 2^{n - Omega(n/log(n))}, making polynomially-sized queries to an NP^{NP} oracle, for computing the permanent of an n x n matrix. The second part of our paper concerns ITS-BQC protocols in which the client and the server engage in one round of quantum communication and then exchange polynomially many classical messages. First, we provide a complexity-theoretic upper bound on the types of functions that could be delegated in such a protocol by showing that they must be contained in QCMA/qpoly cap coQCMA/qpoly. Then, we show that having such a protocol for delegating NP-hard functions implies coNP^{NP^{NP}} subseteq NP^{NP^{PromiseQMA}}.
Cite as

Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, and Elham Kashefi. Complexity-Theoretic Limitations on Blind Delegated Quantum Computation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{aaronson_et_al:LIPIcs.ICALP.2019.6,
  author =	{Aaronson, Scott and Cojocaru, Alexandru and Gheorghiu, Alexandru and Kashefi, Elham},
  title =	{{Complexity-Theoretic Limitations on Blind Delegated Quantum Computation}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.6},
  URN =		{urn:nbn:de:0030-drops-105826},
  doi =		{10.4230/LIPIcs.ICALP.2019.6},
  annote =	{Keywords: Quantum cryptography, Complexity theory, Delegated quantum computation, Computing on encrypted data}
}
Document
DOI: 10.4230/LIPIcs.TQC.2014.176
Blindness and Verification of Quantum Computation with One Pure Qubit

Authors: Theodoros Kapourniotis, Elham Kashefi, and Animesh Datta

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

Abstract
While building a universal quantum computer remains challenging, devices of restricted power such as the so-called one pure qubit model have attracted considerable attention. An important step in the construction of these limited quantum computational devices is the understanding of whether the verification of the computation within these models could be also performed in the restricted scheme. Encoding via blindness (a cryptographic protocol for delegated computing) has proven successful for the verification of universal quantum computation with a restricted verifier. In this paper, we present the adaptation of this approach to the one pure qubit model, and present the first feasible scheme for the verification of delegated one pure qubit model of quantum computing.
Cite as

Theodoros Kapourniotis, Elham Kashefi, and Animesh Datta. Blindness and Verification of Quantum Computation with One Pure Qubit. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 176-204, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{kapourniotis_et_al:LIPIcs.TQC.2014.176,
  author =	{Kapourniotis, Theodoros and Kashefi, Elham and Datta, Animesh},
  title =	{{Blindness and Verification of Quantum Computation with One Pure Qubit}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{176--204},
  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.176},
  URN =		{urn:nbn:de:0030-drops-48151},
  doi =		{10.4230/LIPIcs.TQC.2014.176},
  annote =	{Keywords: Delegated Computing, Verification, Measurement-based Model}
}
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