Search Results

Documents authored by Zhang, Zhicheng

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.59
Strict Hierarchy for Quantum Channel Certification to Unitary

Authors: Kean Chen, Qisheng Wang, and Zhicheng Zhang

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

Abstract
We consider the problem of quantum channel certification to unitary, where one is given access to an unknown d-dimensional channel ℰ, and wants to test whether ℰ is equal to a target unitary channel or is ε-far from it in the diamond norm. We present optimal quantum algorithms for this problem, settling the query complexities in three access models with increasing power. Specifically, we show that: 1) Θ(d/ε²) queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023). 2) Θ(d/ε) queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008). 3) Θ(√d/ε) queries suffice for source-code access model, matching the lower bound due to Jeon and Oh (npj Quantum Inf. 2026). This demonstrates a strict hierarchy of complexities for quantum channel certification to unitary across various access models.
Cite as

Kean Chen, Qisheng Wang, and Zhicheng Zhang. Strict Hierarchy for Quantum Channel Certification to Unitary. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 59:1-59:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2026.59,
  author =	{Chen, Kean and Wang, Qisheng and Zhang, Zhicheng},
  title =	{{Strict Hierarchy for Quantum Channel Certification to Unitary}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{59:1--59:12},
  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.59},
  URN =		{urn:nbn:de:0030-drops-264480},
  doi =		{10.4230/LIPIcs.ICALP.2026.59},
  annote =	{Keywords: Quantum algorithms, quantum channels, quantum certification, query complexity, entanglement fidelity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.154
Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer

Authors: Qisheng Wang and Zhicheng Zhang

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

Abstract
We settle the problem of estimating the trace distance and (square root) fidelity between n-qubit pure quantum states to within additive error ε, given their independent samples, which was raised as an open question by Wang (IEEE Trans. Inf. Theory 2024). This is achieved by a quantum algorithm with optimal sample complexity Θ(1/ε²), improving the long-standing folklore with sample complexity O(1/ε⁴). At the heart of our algorithm is a samplized phase estimation of the product of two Householder reflections. This is realized by an improved (multi-)samplizer for pure states, through which any quantum query algorithm using Q queries to the reflection operator I - 2 |ψ⟩⟨ψ| can be converted to a δ-close (in the diamond norm distance) quantum sample algorithm using Θ(Q²/δ) samples of the state |ψ⟩. This samplizer for pure states is also shown to be optimal.
Cite as

Qisheng Wang and Zhicheng Zhang. Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 154:1-154:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ICALP.2026.154,
  author =	{Wang, Qisheng and Zhang, Zhicheng},
  title =	{{Sample-Optimal Quantum Estimators for Pure-State Trace Distance and Fidelity via Samplizer}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{154:1--154:21},
  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.154},
  URN =		{urn:nbn:de:0030-drops-265433},
  doi =		{10.4230/LIPIcs.ICALP.2026.154},
  annote =	{Keywords: Quantum algorithms, sample complexity, trace distance, fidelity, pure states, lower bounds, samplizer}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.101
Time-Efficient Quantum Entropy Estimator via Samplizer

Authors: Qisheng Wang and Zhicheng Zhang

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Entropy is a measure of the randomness of a system. Estimating the entropy of a quantum state is a basic problem in quantum information. In this paper, we introduce a time-efficient quantum approach to estimating the von Neumann entropy S(ρ) and Rényi entropy S_α(ρ) of an N-dimensional quantum state ρ, given access to independent samples of ρ. Specifically, we provide the following quantum estimators. - A quantum estimator for S(ρ) with time complexity Õ(N²), improving the prior best time complexity Õ(N⁶) by Acharya, Issa, Shende, and Wagner (2020) and Bavarian, Mehraba, and Wright (2016). - A quantum estimator for S_α(ρ) with time complexity Õ(N^{4/α-2}) for 0 < α < 1 and Õ(N^{4-2/α}) for α > 1, improving the prior best time complexity Õ(N^{6/α}) for 0 < α < 1 and Õ(N⁶) for α > 1 by Acharya, Issa, Shende, and Wagner (2020), though at a cost of a slightly larger sample complexity. Moreover, these estimators are naturally extensible to the low-rank case. We also provide a sample lower bound Ω(max{N/ε, N^{1/α-1}/ε^{1/α}}) for estimating S_α(ρ). Technically, our method is quite different from the previous ones that are based on weak Schur sampling and Young diagrams. At the heart of our construction, is a novel tool called samplizer, which can "samplize" a quantum query algorithm to a quantum algorithm with similar behavior using only samples of quantum states; this suggests a unified framework for estimating quantum entropies. Specifically, when a quantum oracle U block-encodes a mixed quantum state ρ, any quantum query algorithm using Q queries to U can be samplized to a δ-close (in the diamond norm) quantum algorithm using Θ~(Q²/δ) samples of ρ. Moreover, this samplization is proven to be optimal, up to a polylogarithmic factor.
Cite as

Qisheng Wang and Zhicheng Zhang. Time-Efficient Quantum Entropy Estimator via Samplizer. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 101:1-101:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ESA.2024.101,
  author =	{Wang, Qisheng and Zhang, Zhicheng},
  title =	{{Time-Efficient Quantum Entropy Estimator via Samplizer}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{101:1--101:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.101},
  URN =		{urn:nbn:de:0030-drops-211722},
  doi =		{10.4230/LIPIcs.ESA.2024.101},
  annote =	{Keywords: Quantum computing, entropy estimation, von Neumann entropy, R\'{e}nyi entropy, sample complexity}
}
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