Harumichi Nishimura

Dhara Thakkar

CoRR, April, 2025

Does there exist a quantum fingerprinting protocol without coherent measurements?

[BibT_eX]

[DOI]

CoRR, February, 2025

Space-Bounded Quantum Interactive Proof Systems.

[BibT_eX]

[DOI]

Proceedings of the 40th Computational Complexity Conference, 2025

2024

On the Power of Quantum Distributed Proofs.

[BibT_eX]

[DOI]

Atsuya Hasegawa

Srijita Kundu

Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, 2024

Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries.

[BibT_eX]

[DOI]

Proceedings of the 28th International Conference on Principles of Distributed Systems, 2024

2023

Distributed Quantum Interactive Proofs.

[BibT_eX]

[DOI]

Masayuki Miyamoto

Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, 2023

Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications.

[BibT_eX]

[DOI]

Masayuki Miyamoto

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

2022

Brief Announcement: Distributed Quantum Interactive Proofs.

[BibT_eX]

[DOI]

Masayuki Miyamoto

Proceedings of the 36th International Symposium on Distributed Computing, 2022

2021

Quantum Logarithmic Space and Post-Selection.

[BibT_eX]

[DOI]

Abuzer Yakaryilmaz

Proceedings of the 16th Conference on the Theory of Quantum Computation, 2021

Distributed Quantum Proofs for Replicated Data.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Communication Complexity of Private Simultaneous Quantum Messages Protocols.

[BibT_eX]

[DOI]

Akinori Kawachi

Proceedings of the 2nd Conference on Information-Theoretic Cryptography, 2021

2020

Rational proofs for quantum computing.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2020

Brief Announcement: Distributed Quantum Proofs for Replicated Data.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Distributed Computing, 2020

2019

Impossibility of blind quantum sampling for classical client.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2019

Quantum Advantage for the LOCAL Model in Distributed Computing.

[BibT_eX]

[DOI]

Ansis Rosmanis

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

2018

Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy.

[BibT_eX]

[DOI]

Yuki Takeuchi

Quantum, 2018

Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

2017

Modified Group Non-Membership is in Promise-AWPP relative to group oracles.

[BibT_eX]

[DOI]

Francois Le Gall

Quantum Inf. Comput., 2017

Merlinization of complexity classes above BQP.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2017

2016

Quantum interpretations of AWPP and APP.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2016

Modified group non-membership is in AWPP.

[BibT_eX]

[DOI]

Francois Le Gall

CoRR, 2016

Power of one non-clean qubit.

[BibT_eX]

[DOI]

Keisuke Fujii

CoRR, 2016

Quantum Merlin-Arthur with noisy channel.

[BibT_eX]

[DOI]

Keisuke Fujii

CoRR, 2016

Quantum Query Complexity of Almost All Functions with Fixed On-set Size.

[BibT_eX]

[DOI]

Comput. Complex., 2016

Power of Quantum Computation with Few Clean Qubits.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Space-Efficient Error Reduction for Unitary Quantum Computations.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Interactive proofs with quantum finite automata.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Quantum Merlin-Arthur with Clifford Arthur.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2015

Power of quantum computing with restricted postselections.

[BibT_eX]

[DOI]

CoRR, 2015

Generalized Quantum Arthur-Merlin Games.

[BibT_eX]

[DOI]

Hirotada Kobayashi

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Impossibility of Classically Simulating One-Clean-Qubit Computation.

[BibT_eX]

[DOI]

CoRR, 2014

Quantum Algorithms for Matrix Products over Semirings.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory - SWAT 2014, 2014

Quantum network coding and the current status of its studies.

[BibT_eX]

[DOI]

Proceedings of the International Symposium on Information Theory and its Applications, 2014

Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs.

[BibT_eX]

[DOI]

Seiichiro Tani

Proceedings of the Computing and Combinatorics - 20th International Conference, 2014

2013

Recovering Strings in Oracles: Quantum and Classic.

[BibT_eX]

[DOI]

Kazuo Iwama

Int. J. Found. Comput. Sci., 2013

Quantum Algorithms for Finding Constant-sized Sub-hypergraphs over 3-uniform Hypergraphs.

[BibT_eX]

[DOI]

Seiichiro Tani

CoRR, 2013

Quantum network coding - How can network coding be applied to quantum information?

[BibT_eX]

[DOI]

Proceedings of the International Symposium on Network Coding, 2013

Stronger methods of making quantum interactive proofs perfectly complete.

[BibT_eX]

[DOI]

Hirotada Kobayashi

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Achieving perfect completeness in classical-witness quantum merlin-arthur proof systems.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2012

On QMA protocols with two short quantum proofs.

[BibT_eX]

[DOI]

Shota Nakagawa

Quantum Inf. Comput., 2012

Reconstructing Strings from Substrings with Quantum Queries.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory - SWAT 2012, 2012

2011

Constructing quantum network coding schemes from classical nonlinear protocols.

[BibT_eX]

[DOI]

Proceedings of the 2011 IEEE International Symposium on Information Theory Proceedings, 2011

2010

Perfect quantum network communication protocol based on classical network coding.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2010

Quantum Counterfeit Coin Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

2009

Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families.

[BibT_eX]

[DOI]

Quantum Inf. Process., 2009

Quantum Random Access Coding.

[BibT_eX]

[DOI]

Rudy Raymond

IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 2009

Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size

[BibT_eX]

[DOI]

CoRR, 2009

General Scheme for Perfect Quantum Network Coding with Free Classical Communication.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

2008

Unbounded-Error Quantum Query Complexity.

[BibT_eX]

[DOI]

Ashley Montanaro

Rudy Raymond

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

Quantum Query Complexity of Boolean Functions with Small On-Sets.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

Polynomial-Time Construction of Linear Network Coding.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

Unbounded-Error Classical and Quantum Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Unbounded-Error One-Way Classical and Quantum Communication Complexity.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006

Quantum Computation with Supplementary Information.

[BibT_eX]

[DOI]

Inf. Media Technol., 2006

(4, 1)-Quantum Random Access Coding Does Not Exist.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 2006 IEEE International Symposium on Information Theory, 2006

Quantum Network Coding.

[BibT_eX]

[DOI]

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

2005

Uniformity of quantum circuit families for error-free algorithms.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2005

Quantum Minimal One Way Information: Relative Hardness and Quantum Advantage of Combinatorial Tasks

[BibT_eX]

[DOI]

CoRR, 2005

Computational Indistinguishability Between Quantum States and Its Cryptographic Application.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 2005

2004

An Application of Quantum Finite Automata to Interactive Proof Systems.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2004

An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

2003

Quantum Computation With Restricted Amplitudes.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2003

Polynomial time quantum computation with advice

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

An Algorithmic Argument for Query Complexity Lower Bounds of Advised Quantum Computation

[BibT_eX]

[DOI]

CoRR, 2003

2002

Computational complexity of uniform quantum circuit families and quantum Turing machines.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

On quantum one-way permutations.

[BibT_eX]

[DOI]

Elham Kashefi

Vlatko Vedral

Quantum Inf. Comput., 2002

On Quantum Computation with Some Restricted Amplitudes.

[BibT_eX]

[DOI]

Proceedings of the STACS 2002, 19th Annual Symposium on Theoretical Aspects of Computer Science, Antibes, 2002

2000

Local transition functions of quantum Turing machines.

[BibT_eX]

[DOI]