4 Search Results for "Hiromasa, Ryo"

Document
DOI: 10.4230/LIPIcs.CCC.2025.12
New Lower-Bounds for Quantum Computation with Non-Collapsing Measurements

Authors: David Miloschewsky and Supartha Podder

Published in: LIPIcs, Volume 339, 40th Computational Complexity Conference (CCC 2025)

Abstract
Aaronson, Bouland, Fitzsimons and Lee [Scott Aaronson et al., 2014] introduced the complexity class PDQP (which was original labeled naCQP), an alteration of BQP enhanced with the ability to obtain non-collapsing measurements, samples of quantum states without collapsing them. Although SZK ⊆ PDQP, it still requires Ω(N^(1/4)) queries to solve unstructured search. We formulate an alternative equivalent definition of PDQP, which we use to prove the positive weighted adversary lower-bounding method, establishing multiple tighter bounds and a trade-off between queries and non-collapsing measurements. We utilize the technique in order to analyze the query complexity of the well-studied majority and element distinctness problems. Additionally, we prove a tight Θ(N^(1/3)) bound on search. Furthermore, we use the lower-bound to explore PDQP under query restrictions, finding that when combined with non-adaptive queries, we limit the speed-up in several cases.
Cite as

David Miloschewsky and Supartha Podder. New Lower-Bounds for Quantum Computation with Non-Collapsing Measurements. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 12:1-12:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{miloschewsky_et_al:LIPIcs.CCC.2025.12,
  author =	{Miloschewsky, David and Podder, Supartha},
  title =	{{New Lower-Bounds for Quantum Computation with Non-Collapsing Measurements}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{12:1--12:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-379-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{339},
  editor =	{Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2025.12},
  URN =		{urn:nbn:de:0030-drops-237067},
  doi =		{10.4230/LIPIcs.CCC.2025.12},
  annote =	{Keywords: Non-collapsing measurements, Quantum lower-bounds, Quantum adversary method}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.96
Formulations and Constructions of Remote State Preparation with Verifiability, with Applications

Authors: Jiayu Zhang

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
Remote state preparation with verifiability (RSPV) is an important quantum cryptographic primitive [Alexandru Gheorghiu and Thomas Vidick, 2019; Jiayu Zhang, 2022]. In this primitive, a client would like to prepare a quantum state (sampled or chosen from a state family) on the server side, such that ideally the client knows its full description, while the server holds and only holds the state itself. In this work we make several contributions on its formulations, constructions and applications. In more detail: - We first work on the definitions and abstract properties of the RSPV problem. We select and compare different variants of definitions [Bennett et al., 2001; Alexandru Gheorghiu and Thomas Vidick, 2019; Jiayu Zhang, 2022; Alexandru Gheorghiu et al., 2022], and study their basic properties (like composability and amplification). - We also study a closely related question of how to certify the server’s operations (instead of solely the states). We introduce a new notion named remote operator application with verifiability (ROAV). We compare this notion with related existing definitions [Summers and Werner, 1987; Dominic Mayers and Andrew Chi-Chih Yao, 2004; Zhengfeng Ji et al., 2021; Tony Metger and Thomas Vidick, 2021; Anand Natarajan and Tina Zhang, 2023], study its abstract properties and leave its concrete constructions for further works. - Building on the abstract properties and existing results [Zvika Brakerski et al., 2023], we construct a series of new RSPV protocols. Our constructions not only simplify existing results [Alexandru Gheorghiu and Thomas Vidick, 2019] but also cover new state families, for example, states in the form of 1/√2 (|0⟩ + |x_0⟩ + |1⟩ |x_1⟩). All these constructions rely only on the existence of weak NTCF [Zvika Brakerski et al., 2020; Navid Alamati et al., 2022], without additional requirements like the adaptive hardcore bit property [Zvika Brakerski et al., 2018; Navid Alamati et al., 2022]. - As a further application, we show that the classical verification of quantum computations (CVQC) problem [Dorit Aharonov et al., 2010; Urmila Mahadev, 2018] could be constructed from assumptions on group actions [Navid Alamati et al., 2020]. This is achieved by combining our results on RSPV with group-action-based instantiation of weak NTCF [Navid Alamati et al., 2022], and then with the quantum-gadget-assisted quantum verification protocol [Ferracin et al., 2018].
Cite as

Jiayu Zhang. Formulations and Constructions of Remote State Preparation with Verifiability, with Applications. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 96:1-96:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{zhang:LIPIcs.ITCS.2025.96,
  author =	{Zhang, Jiayu},
  title =	{{Formulations and Constructions of Remote State Preparation with Verifiability, with Applications}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{96:1--96:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.96},
  URN =		{urn:nbn:de:0030-drops-227245},
  doi =		{10.4230/LIPIcs.ITCS.2025.96},
  annote =	{Keywords: Quantum Cryptography, Remote State Preparation, Self-testing, Verification of Quantum Computations}
}
Document
DOI: 10.4230/LIPIcs.TQC.2023.9
Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection

Authors: Ryo Hiromasa, Akihiro Mizutani, Yuki Takeuchi, and Seiichiro Tani

Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)

Abstract
We define rewinding operators that invert quantum measurements. Then, we define complexity classes RwBQP, CBQP, and AdPostBQP as sets of decision problems solvable by polynomial-size quantum circuits with a polynomial number of rewinding operators, cloning operators, and adaptive postselections, respectively. Our main result is that BPP^PP ⊆ RwBQP = CBQP = AdPostBQP ⊆ PSPACE. As a byproduct of this result, we show that any problem in PostBQP can be solved with only postselections of outputs whose probabilities are polynomially close to one. Under the strongly believed assumption that BQP ⊉ SZK, or the shortest independent vectors problem cannot be efficiently solved with quantum computers, we also show that a single rewinding operator is sufficient to achieve tasks that are intractable for quantum computation. In addition, we consider rewindable Clifford and instantaneous quantum polynomial time circuits.
Cite as

Ryo Hiromasa, Akihiro Mizutani, Yuki Takeuchi, and Seiichiro Tani. Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hiromasa_et_al:LIPIcs.TQC.2023.9,
  author =	{Hiromasa, Ryo and Mizutani, Akihiro and Takeuchi, Yuki and Tani, Seiichiro},
  title =	{{Rewindable Quantum Computation and Its Equivalence to Cloning and Adaptive Postselection}},
  booktitle =	{18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-283-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{266},
  editor =	{Fawzi, Omar and Walter, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.9},
  URN =		{urn:nbn:de:0030-drops-183193},
  doi =		{10.4230/LIPIcs.TQC.2023.9},
  annote =	{Keywords: Quantum computing, Postselection, Lattice problems}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.59
Test of Quantumness with Small-Depth Quantum Circuits

Authors: Shuichi Hirahara and François Le Gall

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
Recently Brakerski, Christiano, Mahadev, Vazirani and Vidick (FOCS 2018) have shown how to construct a test of quantumness based on the learning with errors (LWE) assumption: a test that can be solved efficiently by a quantum computer but cannot be solved by a classical polynomial-time computer under the LWE assumption. This test has lead to several cryptographic applications. In particular, it has been applied to producing certifiable randomness from a single untrusted quantum device, self-testing a single quantum device and device-independent quantum key distribution. In this paper, we show that this test of quantumness, and essentially all the above applications, can actually be implemented by a very weak class of quantum circuits: constant-depth quantum circuits combined with logarithmic-depth classical computation. This reveals novel complexity-theoretic properties of this fundamental test of quantumness and gives new concrete evidence of the superiority of small-depth quantum circuits over classical computation.
Cite as

Shuichi Hirahara and François Le Gall. Test of Quantumness with Small-Depth Quantum Circuits. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 59:1-59:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.MFCS.2021.59,
  author =	{Hirahara, Shuichi and Le Gall, Fran\c{c}ois},
  title =	{{Test of Quantumness with Small-Depth Quantum Circuits}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{59:1--59:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.59},
  URN =		{urn:nbn:de:0030-drops-144996},
  doi =		{10.4230/LIPIcs.MFCS.2021.59},
  annote =	{Keywords: Quantum computing, small-depth circuits, quantum cryptography}
}
  • Refine by Type
  • 4 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2023
  • 1 2021

  • Refine by Author
  • 1 Hirahara, Shuichi
  • 1 Hiromasa, Ryo
  • 1 Le Gall, François
  • 1 Miloschewsky, David
  • 1 Mizutani, Akihiro
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Quantum complexity theory
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Quantum query complexity

  • Refine by Keyword
  • 2 Quantum computing
  • 1 Lattice problems
  • 1 Non-collapsing measurements
  • 1 Postselection
  • 1 Quantum Cryptography
  • Show More...

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