2 Search Results for "Cojocaru, Alexandru"


Document
A Qubit, a Coin, and an Advice String Walk into a Relational Problem

Authors: Scott Aaronson, Harry Buhrman, and William Kretschmer

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)


Abstract
Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FBQP/qpoly, the class of relational problems solvable in quantum polynomial-time with the help of polynomial-sized quantum advice, along with its analogues for deterministic and randomized computation (FP, FBPP) and advice (/poly, /rpoly). Our first result is that FBQP/qpoly ≠ FBQP/poly, unconditionally, with no oracle - a striking contrast with what we know about the analogous decision classes. The proof repurposes the separation between quantum and classical one-way communication complexities due to Bar-Yossef, Jayram, and Kerenidis. We discuss how this separation raises the prospect of near-term experiments to demonstrate "quantum information supremacy," a form of quantum supremacy that would not depend on unproved complexity assumptions. Our second result is that FBPP ̸ ⊂ FP/poly - that is, Adleman’s Theorem fails for relational problems - unless PSPACE ⊂ NP/poly. Our proof uses IP = PSPACE and time-bounded Kolmogorov complexity. On the other hand, we show that proving FBPP ̸ ⊂ FP/poly will be hard, as it implies a superpolynomial circuit lower bound for PromiseBPEXP. We prove the following further results: - Unconditionally, FP ≠ FBPP and FP/poly ≠ FBPP/poly (even when these classes are carefully defined). - FBPP/poly = FBPP/rpoly (and likewise for FBQP). For sampling problems, by contrast, SampBPP/poly ≠ SampBPP/rpoly (and likewise for SampBQP).

Cite as

Scott Aaronson, Harry Buhrman, and William Kretschmer. A Qubit, a Coin, and an Advice String Walk into a Relational Problem. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{aaronson_et_al:LIPIcs.ITCS.2024.1,
  author =	{Aaronson, Scott and Buhrman, Harry and Kretschmer, William},
  title =	{{A Qubit, a Coin, and an Advice String Walk into a Relational Problem}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{1:1--1:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.1},
  URN =		{urn:nbn:de:0030-drops-195290},
  doi =		{10.4230/LIPIcs.ITCS.2024.1},
  annote =	{Keywords: Relational problems, quantum advice, randomized advice, FBQP, FBPP}
}
Document
Track A: Algorithms, Complexity and Games
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-dev.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}
}
  • Refine by Author
  • 2 Aaronson, Scott
  • 1 Buhrman, Harry
  • 1 Cojocaru, Alexandru
  • 1 Gheorghiu, Alexandru
  • 1 Kashefi, Elham
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Quantum complexity theory
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Quantum computation theory

  • Refine by Keyword
  • 1 Complexity theory
  • 1 Computing on encrypted data
  • 1 Delegated quantum computation
  • 1 FBPP
  • 1 FBQP
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2019
  • 1 2024

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