2 Search Results for "Wang, Hung-Lung"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.64
Parallel Self-Testing of EPR Pairs Under Computational Assumptions

Authors: Honghao Fu, Daochen Wang, and Qi Zhao

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
Self-testing is a fundamental feature of quantum mechanics that allows a classical verifier to force untrusted quantum devices to prepare certain states and perform certain measurements on them. The standard approach assumes at least two spatially separated devices. Recently, Metger and Vidick [Metger and Vidick, 2021] showed that a single EPR pair of a single quantum device can be self-tested under computational assumptions. In this work, we generalize their results to give the first parallel self-test of N EPR pairs and measurements on them in the single-device setting under the same computational assumptions. We show that our protocol can be passed with probability negligibly close to 1 by an honest quantum device using poly(N) resources. Moreover, we show that any quantum device that fails our protocol with probability at most ε must be poly(N,ε)-close to being honest in the appropriate sense. In particular, our protocol can test any distribution over tensor products of computational or Hadamard basis measurements, making it suitable for applications such as device-independent quantum key distribution [Metger et al., 2021] under computational assumptions. Moreover, a simplified version of our protocol is the first that can efficiently certify an arbitrary number of qubits of a single cloud quantum computer using only classical communication.
Cite as

Honghao Fu, Daochen Wang, and Qi Zhao. Parallel Self-Testing of EPR Pairs Under Computational Assumptions. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 64:1-64:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fu_et_al:LIPIcs.ICALP.2023.64,
  author =	{Fu, Honghao and Wang, Daochen and Zhao, Qi},
  title =	{{Parallel Self-Testing of EPR Pairs Under Computational Assumptions}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{64:1--64:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.64},
  URN =		{urn:nbn:de:0030-drops-181160},
  doi =		{10.4230/LIPIcs.ICALP.2023.64},
  annote =	{Keywords: Quantum complexity theory, self-testing, LWE}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.10
The Complexity of Packing Edge-Disjoint Paths

Authors: Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, and Hung-Lung Wang

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
We introduce and study the complexity of Path Packing. Given a graph G and a list of paths, the task is to embed the paths edge-disjoint in G. This generalizes the well known Hamiltonian-Path problem. Since Hamiltonian Path is efficiently solvable for graphs of small treewidth, we study how this result translates to the much more general Path Packing. On the positive side, we give an FPT-algorithm on trees for the number of paths as parameter. Further, we give an XP-algorithm with the combined parameters maximal degree, number of connected components and number of nodes of degree at least three. Surprisingly the latter is an almost tight result by runtime and parameterization. We show an ETH lower bound almost matching our runtime. Moreover, if two of the three values are constant and one is unbounded the problem becomes NP-hard. Further, we study restrictions to the given list of paths. On the positive side, we present an FPT-algorithm parameterized by the sum of the lengths of the paths. Packing paths of length two is polynomial time solvable, while packing paths of length three is NP-hard. Finally, even the spacial case Exact Path Packing where the paths have to cover every edge in G exactly once is already NP-hard for two paths on 4-regular graphs.
Cite as

Jan Dreier, Janosch Fuchs, Tim A. Hartmann, Philipp Kuinke, Peter Rossmanith, Bjoern Tauer, and Hung-Lung Wang. The Complexity of Packing Edge-Disjoint Paths. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dreier_et_al:LIPIcs.IPEC.2019.10,
  author =	{Dreier, Jan and Fuchs, Janosch and Hartmann, Tim A. and Kuinke, Philipp and Rossmanith, Peter and Tauer, Bjoern and Wang, Hung-Lung},
  title =	{{The Complexity of Packing Edge-Disjoint Paths}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.10},
  URN =		{urn:nbn:de:0030-drops-114710},
  doi =		{10.4230/LIPIcs.IPEC.2019.10},
  annote =	{Keywords: parameterized complexity, embedding, packing, covering, Hamiltonian path, unary binpacking, path-perfect graphs}
}
  • Refine by Author
  • 1 Dreier, Jan
  • 1 Fu, Honghao
  • 1 Fuchs, Janosch
  • 1 Hartmann, Tim A.
  • 1 Kuinke, Philipp
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Interactive proof systems
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 1 Hamiltonian path
  • 1 LWE
  • 1 Quantum complexity theory
  • 1 covering
  • 1 embedding
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2019
  • 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