25 Search Results for "Nishimura, Harumichi"

Document
DOI: 10.4230/LIPIcs.STACS.2026.66
Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds

Authors: Yupan Liu

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We investigate the computational hardness of estimating the quantum α-Rényi entropy S^𝚁_α(ρ) = (ln Tr(ρ^α))/(1-α) and the quantum q-Tsallis entropy S^𝚃_q(ρ) = (1-Tr(ρ^q))/(q-1), both converging to the von Neumann entropy as the order approaches 1. The promise problems Quantum α-Rényi Entropy Approximation (RényiQEA_α) and Quantum q-Tsallis Entropy Approximation (TsallisQEA_q) ask whether S^𝚁_α(ρ) or S^𝚃_q(ρ), respectively, is at least τ_Y or at most τ_N, where τ_Y - τ_N is typically a positive constant. Previous hardness results cover only the von Neumann entropy (order 1) and some cases of the quantum q-Tsallis entropy, while existing approaches do not readily extend to other orders. We establish that for all positive real orders, the rank-2 variants Rank2RényiQEA_α and Rank2TsallisQEA_q are BQP-hard. Combined with prior (rank-dependent) quantum query algorithms in Wang, Guan, Liu, Zhang, and Ying (TIT 2024), Wang, Zhang, and Li (TIT 2024), and Liu and Wang (SODA 2025), our results imply: - For all real order α > 0 and 0 < q ≤ 1, LowRankRényiQEA_α and LowRankTsallisQEA_q are BQP-complete, where both are restricted versions of RényiQEA_α and TsallisQEA_q with ρ of polynomial rank. - For all real order q > 1, TsallisQEA_q is BQP-complete. Our hardness results stem from reductions based on new inequalities relating the α-Rényi or q-Tsallis binary entropies of different orders, where the reductions differ substantially from previous approaches, and the inequalities are also of independent interest.
Cite as

Yupan Liu. Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 66:1-66:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu:LIPIcs.STACS.2026.66,
  author =	{Liu, Yupan},
  title =	{{Computational Hardness of Estimating Quantum Entropies via Binary Entropy Bounds}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{66:1--66:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.66},
  URN =		{urn:nbn:de:0030-drops-255550},
  doi =		{10.4230/LIPIcs.STACS.2026.66},
  annote =	{Keywords: computational hardness, quantum state testing, quantum R\'{e}nyi entropy, quantum Tsallis entropy, von Neumann entropy}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.34
New Distributed Interactive Proofs for Planarity: A Matter of Left and Right

Authors: Yuval Gil and Merav Parter

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We provide new distributed interactive proofs (DIP) for planarity and related graph families. The notion of a distributed interactive proof (DIP) was introduced by Kol, Oshman, and Saxena (PODC 2018). In this setting, the verifier consists of n nodes connected by a communication graph G. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the graph G satisfies a certain property (e.g., planarity) in a small number of rounds, and with a small communication bound, denoted as the proof size. Prior work by Naor, Parter and Yogev (SODA 2020) presented a DIP for planarity that uses three interaction rounds and a proof size of O(log n). Feuilloley et al. (PODC 2020) showed that the same can be achieved with a single interaction round and without randomization, by providing a proof labeling scheme with a proof size of O(log n). In a subsequent work, Bousquet, Feuilloley, and Pierron (OPODIS 2021) achieved the same bound for related graph families such as outerplanarity, series-parallel graphs, and graphs of treewidth at most 2. In this work, we design new DIPs that use exponentially shorter proofs compared to the state-of-the-art bounds. Our main results are: - There is a 5-round protocol with O(log log n) proof size for outerplanarity. - There is a 5-round protocol with O(log log n) proof size for verifying embedded planarity and O(log log n+log Δ) proof size for general planar graphs, where Δ is the maximum degree in the graph. In the former setting, it is assumed that an embedding of the graph is given (e.g., each node holds a clockwise orientation of its neighbors) and the goal is to verify that it is a valid planar embedding. The latter result should be compared with the non-interactive setting for which there is lower bound of Ω(log n) bits for graphs with Δ = O(1) by Feuilloley et al. (PODC 2020). - The non-interactive deterministic lower bound of Ω(log n) bits by Feuilloley et al. (PODC 2020) can be extended to hold even if the verifier is randomized. Moreover, the lower bound holds even with the assumption that the verifier’s randomness comes in the form of an unbounded random string shared among the nodes. We also show that our DIPs can be extended to protocols with similar bounds for verifying series-parallel graphs and graphs with tree-width at most 2. Perhaps surprisingly, our results demonstrate that the key technical barrier for obtaining o(log log n) labels for all our problems is a basic sorting verification task in which all nodes are embedded on an oriented path P ⊆ G and it is desired for each node to distinguish between its left and right G-neighbors.
Cite as

Yuval Gil and Merav Parter. New Distributed Interactive Proofs for Planarity: A Matter of Left and Right. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 34:1-34:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gil_et_al:LIPIcs.DISC.2025.34,
  author =	{Gil, Yuval and Parter, Merav},
  title =	{{New Distributed Interactive Proofs for Planarity: A Matter of Left and Right}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{34:1--34:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.34},
  URN =		{urn:nbn:de:0030-drops-248515},
  doi =		{10.4230/LIPIcs.DISC.2025.34},
  annote =	{Keywords: Distributed interactive proofs, Planar graphs}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.4
Optimal Quantum Algorithm for Estimating Fidelity to a Pure State

Authors: Wang Fang and Qisheng Wang

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We present an optimal quantum algorithm for fidelity estimation between two quantum states when one of them is pure. In particular, the (square root) fidelity of a mixed state to a pure state can be estimated to within additive error ε by using Θ(1/ε) queries to their state-preparation circuits, achieving a quadratic speedup over the folklore O(1/ε²). Our approach is technically simple, and can moreover estimate the quantity √{tr(ρσ²)} that is not common in the literature. To the best of our knowledge, this is the first query-optimal approach to fidelity estimation involving mixed states.
Cite as

Wang Fang and Qisheng Wang. Optimal Quantum Algorithm for Estimating Fidelity to a Pure State. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fang_et_al:LIPIcs.ESA.2025.4,
  author =	{Fang, Wang and Wang, Qisheng},
  title =	{{Optimal Quantum Algorithm for Estimating Fidelity to a Pure State}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.4},
  URN =		{urn:nbn:de:0030-drops-244727},
  doi =		{10.4230/LIPIcs.ESA.2025.4},
  annote =	{Keywords: Quantum computing, fidelity estimation, quantum algorithms, quantum query complexity}
}
Document
DOI: 10.4230/LIPIcs.TQC.2025.6
Quantum SAT Problems with Finite Sets of Projectors Are Complete for a Plethora of Classes

Authors: Ricardo Rivera Cardoso, Alex Meiburg, and Daniel Nagaj

Published in: LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Abstract
Previously, all known variants of the Quantum Satisfiability (QSAT) problem - consisting of determining whether a k-local (k-body) Hamiltonian is frustration-free - could be classified as being either in 𝖯; or complete for NP, MA, or QMA₁. Here, we present new qubit variants of this problem that are complete for BQP₁, coRP, QCMA, PI(coRP,NP), PI(BQP₁,NP), PI(BQP₁,MA), SoPU(coRP,NP), SoPU(BQP₁,NP), and SoPU(BQP₁,MA). Our result implies that a complete classification of quantum constraint satisfaction problems (QCSPs), analogous to Schaefer’s dichotomy theorem for classical CSPs, must either include these 13 classes, or otherwise show that some are equal. Additionally, our result showcases two new types of QSAT problems that can be decided efficiently, as well as the first nontrivial BQP₁-complete problem. We first construct QSAT problems on qudits that are complete for BQP₁, coRP, and QCMA. These are made by restricting the finite set of Hamiltonians to consist of elements similar to H_{init}, H_{prop}, and H_{out}, seen in the circuit-to-Hamiltonian transformation. Usually, these are used to demonstrate hardness of QSAT and Local Hamiltonian problems, and so our proofs of hardness are simple. The difficulty lies in ensuring that all Hamiltonians generated with these three elements can be decided in their respective classes. For this, we build our Hamiltonian terms with high-dimensional data and clock qudits, ternary logic, and either monogamy of entanglement or specific clock encodings. We then show how to express these problems in terms of qubits, by proving that any QCSP can be reduced to a qubit problem while maintaining the same complexity - something not believed possible classically. The remaining six problems are obtained by considering "sums" and "products" of some of the QSAT problems mentioned here. Before this work, the QSAT problems generated in this way resulted in complete problems for PI and SoPU classes that were trivially equal to NP, MA, or QMA₁. We thus commence the study of these new and seemingly nontrivial classes. While [Meiburg, 2021] first sought to prove completeness for coRP, BQP₁, and QCMA, we note that those constructions are flawed. Here, we rework them, provide correct proofs, and obtain improvements on the required qudit dimensionality.
Cite as

Ricardo Rivera Cardoso, Alex Meiburg, and Daniel Nagaj. Quantum SAT Problems with Finite Sets of Projectors Are Complete for a Plethora of Classes. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{riveracardoso_et_al:LIPIcs.TQC.2025.6,
  author =	{Rivera Cardoso, Ricardo and Meiburg, Alex and Nagaj, Daniel},
  title =	{{Quantum SAT Problems with Finite Sets of Projectors Are Complete for a Plethora of Classes}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{6:1--6:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-392-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{350},
  editor =	{Fefferman, Bill},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.6},
  URN =		{urn:nbn:de:0030-drops-240557},
  doi =		{10.4230/LIPIcs.TQC.2025.6},
  annote =	{Keywords: Quantum complexity theory, quantum satisfiability, circuit-to-Hamiltonian, pairwise union of classes, pairwise intersection of classes}
}
Document
DOI: 10.4230/LIPIcs.TQC.2025.11
Quantum Catalytic Space

Authors: Harry Buhrman, Marten Folkertsma, Ian Mertz, Florian Speelman, Sergii Strelchuk, Sathyawageeswar Subramanian, and Quinten Tupker

Published in: LIPIcs, Volume 350, 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)

Abstract
Space complexity is a key field of study in theoretical computer science. In the quantum setting there are clear motivations to understand the power of space-restricted computation, as qubits are an especially precious and limited resource. Recently, a new branch of space-bounded complexity called catalytic computing has shown that reusing space is a very powerful computational resource, especially for subroutines that incur little to no space overhead. While quantum catalysis in an information theoretic context, and the power of "dirty" qubits for quantum computation, has been studied over the years, these models are generally not suitable for use in quantum space-bounded algorithms, as they either rely on specific catalytic states or destroy the memory being borrowed. We define the notion of catalytic computing in the quantum setting and show a number of initial results about the model. First, we show that quantum catalytic logspace can always be computed quantumly in polynomial time; the classical analogue of this is the largest open question in catalytic computing. This also allows quantum catalytic space to be defined in an equivalent way with respect to circuits instead of Turing machines. We also prove that quantum catalytic logspace can simulate log-depth threshold circuits, a class which is known to contain (and believed to strictly contain) quantum logspace, thus showcasing the power of quantum catalytic space. Finally we show that both unitary quantum catalytic logspace and classical catalytic logspace can be simulated in the one-clean qubit model.
Cite as

Harry Buhrman, Marten Folkertsma, Ian Mertz, Florian Speelman, Sergii Strelchuk, Sathyawageeswar Subramanian, and Quinten Tupker. Quantum Catalytic Space. In 20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 350, pp. 11:1-11:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.TQC.2025.11,
  author =	{Buhrman, Harry and Folkertsma, Marten and Mertz, Ian and Speelman, Florian and Strelchuk, Sergii and Subramanian, Sathyawageeswar and Tupker, Quinten},
  title =	{{Quantum Catalytic Space}},
  booktitle =	{20th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2025)},
  pages =	{11:1--11:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-392-8},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{350},
  editor =	{Fefferman, Bill},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2025.11},
  URN =		{urn:nbn:de:0030-drops-240606},
  doi =		{10.4230/LIPIcs.TQC.2025.11},
  annote =	{Keywords: quantum computing, quantum complexity, space-bounded algorithms, catalytic computation, one clean qubit}
}
Document
DOI: 10.4230/LIPIcs.ITC.2025.9
Revocable Encryption, Programs, and More: The Case of Multi-Copy Security

Authors: Prabhanjan Ananth, Saachi Mutreja, and Alexander Poremba

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
Fundamental principles of quantum mechanics have inspired many new research directions, particularly in quantum cryptography. One such principle is quantum no-cloning which has led to the emerging field of revocable cryptography. Roughly speaking, in a revocable cryptographic primitive, a cryptographic object (such as a ciphertext or program) is represented as a quantum state in such a way that surrendering it effectively translates into losing the capability to use this cryptographic object. All of the revocable cryptographic systems studied so far have a major drawback: the recipient only receives one copy of the quantum state. Worse yet, the schemes become completely insecure if the recipient receives many identical copies of the same quantum state - a property that is clearly much more desirable in practice. While multi-copy security has been extensively studied for a number of other quantum cryptographic primitives, it has so far received only little treatment in context of unclonable primitives. Our work, for the first time, shows the feasibility of revocable primitives, such as revocable encryption and revocable programs, which satisfy multi-copy security in oracle models. This suggest that the stronger notion of multi-copy security is within reach in unclonable cryptography more generally, and therefore could lead to a new research direction in the field.
Cite as

Prabhanjan Ananth, Saachi Mutreja, and Alexander Poremba. Revocable Encryption, Programs, and More: The Case of Multi-Copy Security. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 9:1-9:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ananth_et_al:LIPIcs.ITC.2025.9,
  author =	{Ananth, Prabhanjan and Mutreja, Saachi and Poremba, Alexander},
  title =	{{Revocable Encryption, Programs, and More: The Case of Multi-Copy Security}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{9:1--9:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.9},
  URN =		{urn:nbn:de:0030-drops-243592},
  doi =		{10.4230/LIPIcs.ITC.2025.9},
  annote =	{Keywords: quantum cryptography, unclonable primitives}
}
Document
DOI: 10.4230/LIPIcs.ITC.2025.2
Powerful Primitives in the Bounded Quantum Storage Model

Authors: Mohammed Barhoush and Louis Salvail

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
The bounded quantum storage model aims to achieve security against computationally unbounded adversaries that are restricted only with respect to their quantum memories. In this work, we provide the following contributions in this model: 1) We build one-time programs and utilize them to construct CCA1-secure symmetric key encryption and message authentication codes. These schemes require no quantum memory from honest users, yet they provide information-theoretic security against adversaries with arbitrarily large quantum memories, as long as the transmission length is suitably large. 2) We introduce the notion of k-time program broadcast which is a form of program encryption that allows multiple users to each learn a single evaluation of the encrypted program, while preventing any one user from learning more than k evaluations of the program. We build this primitive unconditionally and employ it to construct CCA1-secure asymmetric key encryption, encryption tokens, signatures, and signature tokens. All these schemes are information-theoretically secure against adversaries with roughly e^√m quantum memory where m is the quantum memory required for the honest user. All of the constructions additionally satisfy disappearing security, essentially preventing an adversary from storing and using a transmission later on.
Cite as

Mohammed Barhoush and Louis Salvail. Powerful Primitives in the Bounded Quantum Storage Model. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{barhoush_et_al:LIPIcs.ITC.2025.2,
  author =	{Barhoush, Mohammed and Salvail, Louis},
  title =	{{Powerful Primitives in the Bounded Quantum Storage Model}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.2},
  URN =		{urn:nbn:de:0030-drops-243523},
  doi =		{10.4230/LIPIcs.ITC.2025.2},
  annote =	{Keywords: Quantum Cryptography, Bounded Quantum Storage Model, Information-Theoretic Security}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.17
Space-Bounded Quantum Interactive Proof Systems

Authors: François Le Gall, Yupan Liu, Harumichi Nishimura, and Qisheng Wang

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

Abstract
We introduce two models of space-bounded quantum interactive proof systems, QIPL and QIP_{U}L. The QIP_{U}L model, a space-bounded variant of quantum interactive proofs (QIP) introduced by Watrous (CC 2003) and Kitaev and Watrous (STOC 2000), restricts verifier actions to unitary circuits. In contrast, QIPL allows logarithmically many pinching intermediate measurements per verifier action, making it the weakest model that encompasses the classical model of Condon and Ladner (JCSS 1995). We characterize the computational power of QIPL and QIP_{U}L. When the message number m is polynomially bounded, QIP_{U}L ⊊ QIPL unless P = NP: - QIPL^HC, a subclass of QIPL defined by a high-concentration condition on yes instances, exactly characterizes NP. - QIP_{U}L is contained in P and contains SAC¹ ∪ BQL, where SAC¹ denotes problems solvable by classical logarithmic-depth, semi-unbounded fan-in circuits. However, this distinction vanishes when m is constant. Our results further indicate that (pinching) intermediate measurements uniquely impact space-bounded quantum interactive proofs, unlike in space-bounded quantum computation, where BQL = BQ_{U}L. We also introduce space-bounded unitary quantum statistical zero-knowledge (QSZK_{U}L), a specific form of QIP_{U}L proof systems with statistical zero-knowledge against any verifier. This class is a space-bounded variant of quantum statistical zero-knowledge (QSZK) defined by Watrous (SICOMP 2009). We prove that QSZK_{U}L = BQL, implying that the statistical zero-knowledge property negates the computational advantage typically gained from the interaction.
Cite as

François Le Gall, Yupan Liu, Harumichi Nishimura, and Qisheng Wang. Space-Bounded Quantum Interactive Proof Systems. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{legall_et_al:LIPIcs.CCC.2025.17,
  author =	{Le Gall, Fran\c{c}ois and Liu, Yupan and Nishimura, Harumichi and Wang, Qisheng},
  title =	{{Space-Bounded Quantum Interactive Proof Systems}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{17:1--17:18},
  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.17},
  URN =		{urn:nbn:de:0030-drops-237115},
  doi =		{10.4230/LIPIcs.CCC.2025.17},
  annote =	{Keywords: Intermediate measurements, Quantum interactive proofs, Space-bounded quantum computation}
}
Document
DOI: 10.4230/LIPIcs.CCC.2025.5
Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks

Authors: Simon C. Marshall, Scott Aaronson, and Vedran Dunjko

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

Abstract
This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the polynomial hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection (PostBQP = PostBPP), (ii) any one of several quantum sampling experiments (BosonSampling, IQP, DQC1) can be approximately performed by a classical computer (contingent on existing assumptions). This last result implies that if any of these experiment’s hardness conjectures hold, then quantum computers can implement functions classical computers cannot (FBQP≠ FBPP) unless the polynomial hierarchy collapses to its 2nd level. These results are an improvement over previous work which either achieved a collapse to the third level or were concerned with exact sampling, a physically impractical case. The workhorse of these results is a new technical complexity-theoretic result which we believe could have value beyond quantum computation. In particular, we prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the polynomial hierarchy collapses to its second level, indeed to ZPP^NP.
Cite as

Simon C. Marshall, Scott Aaronson, and Vedran Dunjko. Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks. In 40th Computational Complexity Conference (CCC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 339, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{marshall_et_al:LIPIcs.CCC.2025.5,
  author =	{Marshall, Simon C. and Aaronson, Scott and Dunjko, Vedran},
  title =	{{Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks}},
  booktitle =	{40th Computational Complexity Conference (CCC 2025)},
  pages =	{5:1--5:14},
  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.5},
  URN =		{urn:nbn:de:0030-drops-236991},
  doi =		{10.4230/LIPIcs.CCC.2025.5},
  annote =	{Keywords: Quantum advantage, Approximate counting, Boson sampling}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.16
Shared Randomness Helps with Local Distributed Problems

Authors: Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, and Jara Uitto

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
By prior work, we have many wonderful results related to distributed graph algorithms for problems that can be defined with local constraints; the formal framework used in prior work is locally checkable labeling problems (LCLs), introduced by Naor and Stockmeyer in the 1990s. It is known, for example, that if we have a deterministic algorithm that solves an LCL in o(log n) rounds, we can speed it up to O(log^* n) rounds, and if we have a randomized algorithm that solves an LCL in O(log^* n) rounds, we can derandomize it for free. It is also known that randomness helps with some LCL problems: there are LCL problems with randomized complexity Θ(log log n) and deterministic complexity Θ(log n). However, so far there have not been any LCL problems in which the use of shared randomness has been necessary; in all prior algorithms it has been enough that the nodes have access to their own private sources of randomness. Could it be the case that shared randomness never helps with LCLs? Could we have a general technique that takes any distributed graph algorithm for any LCL that uses shared randomness, and turns it into an equally fast algorithm where private randomness is enough? In this work we show that the answer is no. We present an LCL problem Π such that the round complexity of Π is Ω(√n) in the usual randomized LOCAL model (with private randomness), but if the nodes have access to a source of shared randomness, then the complexity drops to O(log n). As corollaries, we also resolve several other open questions related to the landscape of distributed computing in the context of LCL problems. In particular, problem Π demonstrates that distributed quantum algorithms for LCL problems strictly benefit from a shared quantum state. Problem Π also gives a separation between finitely dependent distributions and non-signaling distributions.
Cite as

Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikaël Rabie, Jukka Suomela, and Jara Uitto. Shared Randomness Helps with Local Distributed Problems. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.ICALP.2025.16,
  author =	{Balliu, Alkida and Ghaffari, Mohsen and Kuhn, Fabian and Modanese, Augusto and Olivetti, Dennis and Rabie, Mika\"{e}l and Suomela, Jukka and Uitto, Jara},
  title =	{{Shared Randomness Helps with Local Distributed Problems}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.16},
  URN =		{urn:nbn:de:0030-drops-233931},
  doi =		{10.4230/LIPIcs.ICALP.2025.16},
  annote =	{Keywords: Distributed computing, locally checkable labelings, shared randomness}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.34
Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries

Authors: François Le Gall, Oran Nadler, Harumichi Nishimura, and Rotem Oshman

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
In this paper we study a quantum version of the multiparty simultaneous message-passing (SMP) model, and we show that in some cases, quantum communication can replace public randomness, even with no entanglement between the parties. This was already known for two players, but not for more than two players, and indeed, so far all that was known was a negative result. Our main technical contribution is a compiler that takes any classical public-coin simultaneous protocol based on "modified equality queries," and converts it into a quantum simultaneous protocol without public coins with roughly the same communication complexity. We then use our compiler to derive protocols for several problems, including frequency moments, neighborhood diversity, enumeration of isolated cliques, and more.
Cite as

François Le Gall, Oran Nadler, Harumichi Nishimura, and Rotem Oshman. Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 34:1-34:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{legall_et_al:LIPIcs.OPODIS.2024.34,
  author =	{Le Gall, Fran\c{c}ois and Nadler, Oran and Nishimura, Harumichi and Oshman, Rotem},
  title =	{{Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{34:1--34:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.34},
  URN =		{urn:nbn:de:0030-drops-225701},
  doi =		{10.4230/LIPIcs.OPODIS.2024.34},
  annote =	{Keywords: SMP model, multi-party communication, quantum distributed algorithms}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.63
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications

Authors: François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
The generation and verification of quantum states are fundamental tasks for quantum information processing that have recently been investigated by Irani, Natarajan, Nirkhe, Rao and Yuen [CCC 2022], Rosenthal and Yuen [ITCS 2022], Metger and Yuen [QIP 2023] under the term state synthesis. This paper studies this concept from the viewpoint of quantum distributed computing, and especially distributed quantum Merlin-Arthur (dQMA) protocols. We first introduce a novel task, on a line, called state generation with distributed inputs (SGDI). In this task, the goal is to generate the quantum state U|ψ⟩ at the rightmost node of the line, where |ψ⟩ is a quantum state given at the leftmost node and U is a unitary matrix whose description is distributed over the nodes of the line. We give a dQMA protocol for SGDI and utilize this protocol to construct a dQMA protocol for the Set Equality problem studied by Naor, Parter and Yogev [SODA 2020], and complement our protocol by showing classical lower bounds for this problem. Our second contribution is a dQMA protocol, based on a recent work by Zhu and Hayashi [Physical Review A, 2019], to create EPR-pairs between adjacent nodes of a network without quantum communication. As an application of this dQMA protocol, we prove a general result showing how to convert any dQMA protocol on an arbitrary network into another dQMA protocol where the verification stage does not require any quantum communication.
Cite as

François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{legall_et_al:LIPIcs.MFCS.2023.63,
  author =	{Le Gall, Fran\c{c}ois and Miyamoto, Masayuki and Nishimura, Harumichi},
  title =	{{Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{63:1--63:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.63},
  URN =		{urn:nbn:de:0030-drops-185975},
  doi =		{10.4230/LIPIcs.MFCS.2023.63},
  annote =	{Keywords: distributed quantum Merlin-Arthur, distributed verification, quantum computation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2023.42
Distributed Quantum Interactive Proofs

Authors: François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract
The study of distributed interactive proofs was initiated by Kol, Oshman, and Saxena [PODC 2018] as a generalization of distributed decision mechanisms (proof-labeling schemes, etc.), and has received a lot of attention in recent years. In distributed interactive proofs, the nodes of an n-node network G can exchange short messages (called certificates) with a powerful prover. The goal is to decide if the input (including G itself) belongs to some language, with as few turns of interaction and as few bits exchanged between nodes and the prover as possible. There are several results showing that the size of certificates can be reduced drastically with a constant number of interactions compared to non-interactive distributed proofs. In this paper, we introduce the quantum counterpart of distributed interactive proofs: certificates can now be quantum bits, and the nodes of the network can perform quantum computation. The first result of this paper shows that by using distributed quantum interactive proofs, the number of interactions can be significantly reduced. More precisely, our result shows that for any constant k, the class of languages that can be decided by a k-turn classical (i.e., non-quantum) distributed interactive protocol with f(n)-bit certificate size is contained in the class of languages that can be decided by a 5-turn distributed quantum interactive protocol with O(f(n))-bit certificate size. We also show that if we allow to use shared randomness, the number of turns can be reduced to three. Since no similar turn-reduction classical technique is currently known, our result gives evidence of the power of quantum computation in the setting of distributed interactive proofs as well. As a corollary of our results, we show that there exist 5-turn/3-turn distributed quantum interactive protocols with small certificate size for problems that have been considered in prior works on distributed interactive proofs such as [Kol, Oshman, and Saxena PODC 2018, Naor, Parter, and Yogev SODA 2020]. We then utilize the framework of the distributed quantum interactive proofs to test closeness of two quantum states each of which is distributed over the entire network.
Cite as

François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Distributed Quantum Interactive Proofs. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 42:1-42:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{legall_et_al:LIPIcs.STACS.2023.42,
  author =	{Le Gall, Fran\c{c}ois and Miyamoto, Masayuki and Nishimura, Harumichi},
  title =	{{Distributed Quantum Interactive Proofs}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{42:1--42:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.42},
  URN =		{urn:nbn:de:0030-drops-176949},
  doi =		{10.4230/LIPIcs.STACS.2023.42},
  annote =	{Keywords: distributed interactive proofs, distributed verification, quantum computation}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.48
Brief Announcement: Distributed Quantum Interactive Proofs

Authors: François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
The study of distributed interactive proofs was initiated by Kol, Oshman, and Saxena [PODC 2018] as a generalization of distributed decision mechanisms (proof-labeling schemes, etc.), and has received a lot of attention in recent years. In distributed interactive proofs, the nodes of an n-node network G can exchange short messages (called certificates) with a powerful prover. The goal is to decide if the input (including G itself) belongs to some language, with as few turns of interaction and as few bits exchanged between nodes and the prover as possible. There are several results showing that the size of certificates can be reduced drastically with a constant number of interactions compared to non-interactive distributed proofs. In this brief announcement, we introduce the quantum counterpart of distributed interactive proofs: certificates can now be quantum bits, and the nodes of the network can perform quantum computation. The main result of this paper shows that by using quantum distributed interactive proofs, the number of interactions can be significantly reduced. More precisely, our main result shows that for any constant k, the class of languages that can be decided by a k-turn classical (i.e., non-quantum) distributed interactive protocol with f(n)-bit certificate size is contained in the class of languages that can be decided by a 5-turn distributed quantum interactive protocol with O(f(n))-bit certificate size. We also show that if we allow to use shared randomness, the number of turns can be reduced to 3-turn. Since no similar turn-reduction classical technique is currently known, our result gives evidence of the power of quantum computation in the setting of distributed interactive proofs as well.
Cite as

François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura. Brief Announcement: Distributed Quantum Interactive Proofs. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 48:1-48:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{legall_et_al:LIPIcs.DISC.2022.48,
  author =	{Le Gall, Fran\c{c}ois and Miyamoto, Masayuki and Nishimura, Harumichi},
  title =	{{Brief Announcement: Distributed Quantum Interactive Proofs}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{48:1--48:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.48},
  URN =		{urn:nbn:de:0030-drops-172396},
  doi =		{10.4230/LIPIcs.DISC.2022.48},
  annote =	{Keywords: distributed interactive proofs, distributed verification, quantum computation}
}
Document
DOI: 10.4230/LIPIcs.ITC.2021.20
Communication Complexity of Private Simultaneous Quantum Messages Protocols

Authors: Akinori Kawachi and Harumichi Nishimura

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)

Abstract
The private simultaneous messages (PSM) model is a non-interactive version of the multiparty secure computation (MPC), which has been intensively studied to examine the communication cost of the secure computation. We consider its quantum counterpart, the private simultaneous quantum messages (PSQM) model, and examine the advantages of quantum communication and prior entanglement of this model. In the PSQM model, k parties P₁,…,P_k initially share a common random string (or entangled states in a stronger setting), and they have private classical inputs x₁,…, x_k. Every P_i generates a quantum message from the private input x_i and the shared random string (entangled states), and then sends it to the referee R. Receiving the messages from the k parties, R computes F(x₁,…,x_k) from the messages. Then, R learns nothing except for F(x₁,…,x_k) as the privacy condition. We obtain the following results for this PSQM model. (i) We demonstrate that the privacy condition inevitably increases the communication cost in the two-party PSQM model as well as in the classical case presented by Applebaum, Holenstein, Mishra, and Shayevitz [Journal of Cryptology(3), 916-953 (2020)]. In particular, we prove a lower bound (3-o(1))n of the communication complexity in PSQM protocols with a shared random string for random Boolean functions of 2n-bit input, which is larger than the trivial upper bound 2n of the communication complexity without the privacy condition. (ii) We demonstrate a factor two gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings by designing a multiparty PSQM protocol with shared entangled states for a total function that extends the two-party equality function. (iii) We demonstrate an exponential gap between the communication complexity of PSQM protocols with shared entangled states and with shared random strings for a two-party partial function.
Cite as

Akinori Kawachi and Harumichi Nishimura. Communication Complexity of Private Simultaneous Quantum Messages Protocols. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 20:1-20:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kawachi_et_al:LIPIcs.ITC.2021.20,
  author =	{Kawachi, Akinori and Nishimura, Harumichi},
  title =	{{Communication Complexity of Private Simultaneous Quantum Messages Protocols}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{20:1--20:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.20},
  URN =		{urn:nbn:de:0030-drops-143393},
  doi =		{10.4230/LIPIcs.ITC.2021.20},
  annote =	{Keywords: Communication complexity, private simultaneous messages, quantum protocols, secure multi-party computation}
}
  • Refine by Type
  • 25 Document/PDF
  • 11 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 10 2025
  • 2 2023
  • 1 2022
  • 3 2021
  • Show More...

  • Refine by Author
  • 15 Nishimura, Harumichi
  • 11 Le Gall, François
  • 3 Kobayashi, Hirotada
  • 3 Miyamoto, Masayuki
  • 3 Morimae, Tomoyuki
  • Show More...

  • Refine by Series/Journal
  • 24 LIPIcs
  • 1 DagSemProc

  • Refine by Classification
  • 8 Theory of computation → Quantum computation theory
  • 5 Theory of computation → Distributed algorithms
  • 4 Theory of computation → Quantum complexity theory
  • 3 Theory of computation → Complexity classes
  • 3 Theory of computation → Quantum communication complexity
  • Show More...

  • Refine by Keyword
  • 4 Quantum computing
  • 4 quantum computation
  • 4 quantum computing
  • 3 distributed verification
  • 2 Algorithmic Aspects of Networks
  • 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