4 Search Results for "Liu, Qipeng"


Document
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.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
Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More

Authors: Qipeng Liu

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


Abstract
With the power of quantum information, we can achieve exciting and classically impossible cryptographic primitives. However, almost all quantum cryptography faces extreme difficulties with the near-term intermediate-scale quantum technology (NISQ technology); namely, the short lifespan of quantum states and limited sequential computation. At the same time, considering only limited quantum adversaries may still enable us to achieve never-before-possible tasks. In this work, we consider quantum cryptographic primitives against limited quantum adversaries - depth-bounded adversaries. We introduce a model for (depth-bounded) NISQ computers, which are classical circuits interleaved with shallow quantum circuits. Then, we show one-time memory can be achieved against any depth-bounded quantum adversaries introduced in the work, with their depth being any pre-fixed polynomial. Therefore we obtain applications like one-time programs and one-time proofs. Finally, we show our one-time memory has correctness even against constant-rate errors.

Cite as

Qipeng Liu. Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 82:1-82:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{liu:LIPIcs.ITCS.2023.82,
  author =	{Liu, Qipeng},
  title =	{{Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{82:1--82:18},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.82},
  URN =		{urn:nbn:de:0030-drops-175859},
  doi =		{10.4230/LIPIcs.ITCS.2023.82},
  annote =	{Keywords: cryptographic protocol, one-time memory, quantum cryptography}
}
Document
Beating Classical Impossibility of Position Verification

Authors: Jiahui Liu, Qipeng Liu, and Luowen Qian

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


Abstract
Chandran et al. (SIAM J. Comput. '14) formally introduced the cryptographic task of position verification, where they also showed that it cannot be achieved by classical protocols. In this work, we initiate the study of position verification protocols with classical verifiers. We identify that proofs of quantumness (and thus computational assumptions) are necessary for such position verification protocols. For the other direction, we adapt the proof of quantumness protocol by Brakerski et al. (FOCS '18) to instantiate such a position verification protocol. As a result, we achieve classically verifiable position verification assuming the quantum hardness of Learning with Errors. Along the way, we develop the notion of 1-of-2 non-local soundness for a natural non-local game for 1-of-2 puzzles, first introduced by Radian and Sattath (AFT '19), which can be viewed as a computational unclonability property. We show that 1-of-2 non-local soundness follows from the standard 2-of-2 soundness (and therefore the adaptive hardcore bit property), which could be of independent interest.

Cite as

Jiahui Liu, Qipeng Liu, and Luowen Qian. Beating Classical Impossibility of Position Verification. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 100:1-100:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.ITCS.2022.100,
  author =	{Liu, Jiahui and Liu, Qipeng and Qian, Luowen},
  title =	{{Beating Classical Impossibility of Position Verification}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{100:1--100:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.100},
  URN =		{urn:nbn:de:0030-drops-156963},
  doi =		{10.4230/LIPIcs.ITCS.2022.100},
  annote =	{Keywords: cryptographic protocol, position verification, quantum cryptography, proof of quantumness, non-locality}
}
Document
Quantum Pseudorandomness and Classical Complexity

Authors: William Kretschmer

Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)


Abstract
We construct a quantum oracle relative to which BQP = QMA but cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist, a counterintuitive result in light of the fact that pseudorandom states can be "broken" by quantum Merlin-Arthur adversaries. We explain how this nuance arises as the result of a distinction between algorithms that operate on quantum and classical inputs. On the other hand, we show that some computational complexity assumption is needed to construct pseudorandom states, by proving that pseudorandom states do not exist if BQP = PP. We discuss implications of these results for cryptography, complexity theory, and quantum tomography.

Cite as

William Kretschmer. Quantum Pseudorandomness and Classical Complexity. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{kretschmer:LIPIcs.TQC.2021.2,
  author =	{Kretschmer, William},
  title =	{{Quantum Pseudorandomness and Classical Complexity}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.2},
  URN =		{urn:nbn:de:0030-drops-139975},
  doi =		{10.4230/LIPIcs.TQC.2021.2},
  annote =	{Keywords: pseudorandom quantum states, quantum Merlin-Arthur}
}
  • Refine by Author
  • 3 Liu, Qipeng
  • 1 Kretschmer, William
  • 1 Li, Xingjian
  • 1 Liu, Jiahui
  • 1 Pelecanos, Angelos
  • Show More...

  • Refine by Classification
  • 2 Security and privacy → Authorization
  • 2 Security and privacy → Public key (asymmetric) techniques
  • 2 Theory of computation → Cryptographic protocols
  • 2 Theory of computation → Quantum complexity theory
  • 1 Theory of computation → Complexity classes
  • Show More...

  • Refine by Keyword
  • 2 cryptographic protocol
  • 2 quantum cryptography
  • 1 computational complexity
  • 1 non-locality
  • 1 one-time memory
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2021
  • 1 2022
  • 1 2023
  • 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