3 Search Results for "Yamakawa, Takashi"

Document
DOI: 10.4230/LIPIcs.ITCS.2024.72
Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle

Authors: Xingjian Li, Qipeng Liu, Angelos Pelecanos, and Takashi Yamakawa

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

Abstract
It is a long-standing open question to construct a classical oracle relative to which BQP/qpoly ≠ BQP/poly or QMA ≠ QCMA. In this paper, we construct classically-accessible classical oracles relative to which BQP/qpoly ≠ BQP/poly and QMA ≠ QCMA. Here, classically-accessible classical oracles are oracles that can be accessed only classically even for quantum algorithms. Based on a similar technique, we also show an alternative proof for the separation of QMA and QCMA relative to a distributional quantumly-accessible classical oracle, which was recently shown by Natarajan and Nirkhe.
Cite as

Xingjian Li, Qipeng Liu, Angelos Pelecanos, and Takashi Yamakawa. Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 72:1-72:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ITCS.2024.72,
  author =	{Li, Xingjian and Liu, Qipeng and Pelecanos, Angelos and Yamakawa, Takashi},
  title =	{{Classical vs Quantum Advice and Proofs Under Classically-Accessible Oracle}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{72:1--72:19},
  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.72},
  URN =		{urn:nbn:de:0030-drops-196009},
  doi =		{10.4230/LIPIcs.ITCS.2024.72},
  annote =	{Keywords: quantum computation, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.75
Total NP Search Problems with Abundant Solutions

Authors: Jiawei Li

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

Abstract
We define a new complexity class TFAP to capture TFNP problems that possess abundant solutions for each input. We identify several problems across diverse fields that belong to TFAP, including WeakPigeon (finding a collision in a mapping from [2n] pigeons to [n] holes), Yamakawa-Zhandry’s problem [Takashi Yamakawa and Mark Zhandry, 2022], and all problems in TFZPP. Conversely, we introduce the notion of "semi-gluability" to characterize TFNP problems that could have a unique or a very limited number of solutions for certain inputs. We prove that there is no black-box reduction from any "semi-gluable" problems to any TFAP problems. Furthermore, it can be extended to rule out randomized black-box reduction in most cases. We identify that the majority of common TFNP subclasses, including PPA, PPAD, PPADS, PPP, PLS, CLS, SOPL, and UEOPL, are "semi-gluable". This leads to a broad array of oracle separation results within TFNP regime. As a corollary, UEOPL^O ⊈ PWPP^O relative to an oracle O.
Cite as

Jiawei Li. Total NP Search Problems with Abundant Solutions. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 75:1-75:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{li:LIPIcs.ITCS.2024.75,
  author =	{Li, Jiawei},
  title =	{{Total NP Search Problems with Abundant Solutions}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{75:1--75:23},
  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.75},
  URN =		{urn:nbn:de:0030-drops-196031},
  doi =		{10.4230/LIPIcs.ITCS.2024.75},
  annote =	{Keywords: TFNP, Pigeonhole Principle}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.87
Proofs of Quantumness from Trapdoor Permutations

Authors: Tomoyuki Morimae and Takashi Yamakawa

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Assume that Alice can do only classical probabilistic polynomial-time computing while Bob can do quantum polynomial-time computing. Alice and Bob communicate over only classical channels, and finally Bob gets a state |x₀⟩+|x₁⟩ with some bit strings x₀ and x₁. Is it possible that Alice can know {x₀,x₁} but Bob cannot? Such a task, called remote state preparations, is indeed possible under some complexity assumptions, and is bases of many quantum cryptographic primitives such as proofs of quantumness, (classical-client) blind quantum computing, (classical) verifications of quantum computing, and quantum money. A typical technique to realize remote state preparations is to use 2-to-1 trapdoor collision resistant hash functions: Alice sends a 2-to-1 trapdoor collision resistant hash function f to Bob, and Bob evaluates it coherently, i.e., Bob generates ∑_x|x⟩|f(x)⟩. Bob measures the second register to get the measurement result y, and sends y to Alice. Bob’s post-measurement state is |x₀⟩+|x₁⟩, where f(x₀) = f(x₁) = y. With the trapdoor, Alice can learn {x₀,x₁} from y, but due to the collision resistance, Bob cannot. This Alice’s advantage can be leveraged to realize the quantum cryptographic primitives listed above. It seems that the collision resistance is essential here. In this paper, surprisingly, we show that the collision resistance is not necessary for a restricted case: we show that (non-verifiable) remote state preparations of |x₀⟩+|x₁⟩ secure against classical probabilistic polynomial-time Bob can be constructed from classically-secure (full-domain) trapdoor permutations. Trapdoor permutations are not likely to imply the collision resistance, because black-box reductions from collision-resistant hash functions to trapdoor permutations are known to be impossible. As an application of our result, we construct proofs of quantumness from classically-secure (full-domain) trapdoor permutations.
Cite as

Tomoyuki Morimae and Takashi Yamakawa. Proofs of Quantumness from Trapdoor Permutations. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 87:1-87:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{morimae_et_al:LIPIcs.ITCS.2023.87,
  author =	{Morimae, Tomoyuki and Yamakawa, Takashi},
  title =	{{Proofs of Quantumness from Trapdoor Permutations}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{87:1--87:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.87},
  URN =		{urn:nbn:de:0030-drops-175900},
  doi =		{10.4230/LIPIcs.ITCS.2023.87},
  annote =	{Keywords: Quantum cryptography, Proofs of quantumness, Trapdoor permutations}
}
  • Refine by Author
  • 2 Yamakawa, Takashi
  • 1 Li, Jiawei
  • 1 Li, Xingjian
  • 1 Liu, Qipeng
  • 1 Morimae, Tomoyuki
  • Show More...

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

  • Refine by Keyword
  • 1 Pigeonhole Principle
  • 1 Proofs of quantumness
  • 1 Quantum cryptography
  • 1 TFNP
  • 1 Trapdoor permutations
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2024
  • 1 2023

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