Search Results

Documents authored by Wu, Pei

Document
DOI: 10.4230/LIPIcs.TQC.2026.5
Quantum Merlin-Arthur with an Internally Separable Proof

Authors: Roozbeh Bassirian, Bill Fefferman, Itai Leigh, Kunal Marwaha, and Pei Wu

Published in: LIPIcs, Volume 389, 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026)

Abstract
While the role of entanglement in quantum proof systems has been extensively studied, the computational power of unentanglement remains poorly understood. Since entanglement admits many inequivalent multipartite structures, it is natural to ask how more fine-grained structural promises affect computational power. In this work we investigate a mild promise: each proof is internally separable, meaning that after tracing out one register, a designated constant-size subsystem is separable from the rest - even though the overall proof may still be entangled across every bipartition. We prove a qualitative jump from one proof to two: with one internally separable proof, the resulting class is contained in EXP (even allowing an inverse-exponential completeness–soundness gap), whereas with two unentangled internally separable proofs, the class equals NEXP at constant gap. Notably, in the NEXP construction, the second proof is used solely to implement a SWAP-based purity test.
Cite as

Roozbeh Bassirian, Bill Fefferman, Itai Leigh, Kunal Marwaha, and Pei Wu. Quantum Merlin-Arthur with an Internally Separable Proof. In 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 389, pp. 5:1-5:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bassirian_et_al:LIPIcs.TQC.2026.5,
  author =	{Bassirian, Roozbeh and Fefferman, Bill and Leigh, Itai and Marwaha, Kunal and Wu, Pei},
  title =	{{Quantum Merlin-Arthur with an Internally Separable Proof}},
  booktitle =	{21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026)},
  pages =	{5:1--5:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-439-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{389},
  editor =	{Arnon, Rotem 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.2026.5},
  URN =		{urn:nbn:de:0030-drops-273022},
  doi =		{10.4230/LIPIcs.TQC.2026.5},
  annote =	{Keywords: entanglement structures, unentanglement, quantum complexity, QMA(2), NEXP}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2026.78
Randomized and Quantum Lifting for One-Way Conservative NOF Model

Authors: Haoyu Wang and Pei Wu

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract
We consider lifting theorems that transfer lower bounds for two-party communication problems to multiparty communication problems. In particular, following the deterministic Number-on-Forehead (NOF) lifting framework of Yang and Zhang, we study randomized and quantum one-way NOF lifting for composed problems F(z,𝐱) = f(z,G(𝐱)). We work in a one-way NOF model in which only the last player’s view is restricted. The other players have their usual NOF views and communicate as usual, but the last player sees only the gadget output G(𝐱), not the gadget input 𝐱. This kind of restricted-view has appeared in the NOF literature under the name conservative model. Our main contribution is a pair of lifting theorems for this model. In the randomized setting, we show that lifting follows when each preimage G^{-1}(v), the set of gadget inputs with output v, looks pseudorandom to large cylinder intersections. In the quantum setting, we prove an analogous theorem. Equivalently, conservative protocols for F(z,𝐱) = f(z,G(𝐱)) can be converted into two-party one-way protocols for f(z,v) with comparable cost, and the error loss controlled by the corresponding pseudorandomness parameters. Thus, this restriction isolates a setting in which both randomized and quantum one-way NOF lifting can be proved by a direct simulation argument. We prove the required pseudorandomness properties for the generalized inner product gadget over finite fields, using the multiparty character-sum bounds of Yang and Zhang, and for random gadgets, which give non-explicit lifting. As applications, Boolean Hidden Matching yields a randomized-versus-quantum separation in the conservative NOF model, and lifting INDEX gives randomized and quantum conservative NOF lower bounds for O(log n) players.
Cite as

Haoyu Wang and Pei Wu. Randomized and Quantum Lifting for One-Way Conservative NOF Model. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 78:1-78:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.MFCS.2026.78,
  author =	{Wang, Haoyu and Wu, Pei},
  title =	{{Randomized and Quantum Lifting for One-Way Conservative NOF Model}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{78:1--78:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.78},
  URN =		{urn:nbn:de:0030-drops-274604},
  doi =		{10.4230/LIPIcs.MFCS.2026.78},
  annote =	{Keywords: communication complexity, lifting theorem, number-on-forehead model}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.97
Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding

Authors: Amin Shiraz Gilani, Daochen Wang, Pei Wu, and Xingyu Zhou

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
The edge list model is arguably the simplest input model for graphs, where the graph is specified by a list of its edges. In this model, we study the quantum query complexity of three variants of the triangle finding problem. The first asks whether there exists a triangle containing a target edge and raises general questions about the hiding of a problem’s input among irrelevant data. The second asks whether there exists a triangle containing a target vertex and raises general questions about the shuffling of a problem’s input. The third asks whether there exists a triangle; this problem bridges the 3-distinctness and 3-sum problems, which have been extensively studied by both cryptographers and complexity theorists. We provide tight or nearly tight results for these problems as well as some first answers to the general questions they raise. Furthermore, given any graph with low maximum degree, such as a typical random sparse graph, we prove that the quantum query complexity of finding a length-k cycle in its length-m edge list is m^{3/4-1/(2^{k+2}-4) ± o(1)}, which matches the best-known upper bound for the quantum query complexity of k-distinctness on length-m inputs up to an m^o(1) factor. We prove the lower bound by developing new techniques within Zhandry’s recording query framework [Zhandry, 2019] as generalized by Hamoudi and Magniez [Hamoudi and Magniez, 2023]. These techniques extend the framework to treat any non-product distribution that results from conditioning a product distribution on the absence of rare events. We prove the upper bound by adapting Belovs’s learning graph algorithm for k-distinctness [Belovs, 2012]. Finally, assuming a plausible conjecture concerning only cycle finding, we show that the lower bound can be lifted to an essentially tight lower bound on the quantum query complexity of k-distinctness, which is a long-standing open question.
Cite as

Amin Shiraz Gilani, Daochen Wang, Pei Wu, and Xingyu Zhou. Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 97:1-97:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gilani_et_al:LIPIcs.ICALP.2026.97,
  author =	{Gilani, Amin Shiraz and Wang, Daochen and Wu, Pei and Zhou, Xingyu},
  title =	{{Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{97:1--97:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.97},
  URN =		{urn:nbn:de:0030-drops-264867},
  doi =		{10.4230/LIPIcs.ICALP.2026.97},
  annote =	{Keywords: Quantum query complexity, graph algorithms, edge list model}
}
Document
DOI: 10.4230/LIPIcs.CCC.2024.26
Dimension Independent Disentanglers from Unentanglement and Applications

Authors: Fernando Granha Jeronimo and Pei Wu

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract
Quantum entanglement, a distinctive form of quantum correlation, has become a key enabling ingredient in diverse applications in quantum computation, complexity, cryptography, etc. However, the presence of unwanted adversarial entanglement also poses challenges and even prevents the correct behaviour of many protocols and applications. In this paper, we explore methods to "break" the quantum correlations. Specifically, we construct a dimension-independent k-partite disentangler (like) channel from bipartite unentangled input. In particular, we show: For every d,𝓁 ≥ k ∈ ℕ^+, there is an efficient channel Λ : ℂ^{d𝓁} ⊗ ℂ^{d𝓁} → ℂ^{dk} such that for every bipartite separable density operator ρ₁⊗ ρ₂, the output Λ(ρ₁⊗ρ₂) is close to a k-partite separable state. Concretely, for some distribution μ on states from C^d, ║ Λ(ρ₁⊗ρ₂) - ∫ |ψ⟩⟨ψ|^{⊗k} dμ(ψ) ║₁ ≤ Õ((k³/𝓁)^{1/4}). Moreover, Λ(|ψ⟩⟨ψ|^{⊗𝓁} ⊗ |ψ⟩⟨ψ|^{⊗𝓁}) = |ψ⟩⟨ψ|^{⊗k}. Without the bipartite unentanglement assumption, the above bound is conjectured to be impossible and would imply QMA(2) = QMA. Leveraging multipartite unentanglement ensured by our disentanglers, we achieve the following: (i) a new proof that QMA(2) admits arbitrary gap amplification; (ii) a variant of the swap test and product test with improved soundness, addressing a major limitation of their original versions. More importantly, we demonstrate that unentangled quantum proofs of almost general real amplitudes capture NEXP, thereby greatly relaxing the non-negative amplitudes assumption in the recent work of QMA^+(2) = NEXP [Jeronimo and Wu, STOC 2023]. Specifically, our findings show that to capture NEXP, it suffices to have unentangled proofs of the form |ψ⟩ = √a |ψ_{+}⟩ + √{1-a} |ψ_{-}⟩ where |ψ_{+}⟩ has non-negative amplitudes, |ψ_{-}⟩ only has negative amplitudes and |a-(1-a)| ≥ 1/poly(n) with a ∈ [0,1]. Additionally, we present a protocol achieving an almost largest possible completeness-soundness gap before obtaining QMA^ℝ(k) = NEXP, namely, a 1/poly(n) additive improvement to the gap results in this equality.
Cite as

Fernando Granha Jeronimo and Pei Wu. Dimension Independent Disentanglers from Unentanglement and Applications. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 26:1-26:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{jeronimo_et_al:LIPIcs.CCC.2024.26,
  author =	{Jeronimo, Fernando Granha and Wu, Pei},
  title =	{{Dimension Independent Disentanglers from Unentanglement and Applications}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{26:1--26:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.26},
  URN =		{urn:nbn:de:0030-drops-204228},
  doi =		{10.4230/LIPIcs.CCC.2024.26},
  annote =	{Keywords: QMA(2), disentangler, quantum proofs}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact