Journal/Conference Proceedings

• Atsuya Hasegawa, Srijita Kundu, Harumichi Nishimura, On the Power of Quantum Distributed Proofs, in Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC2024), pp.220-230 (2024).
• Francois Le Gall, Masayuki Miyamoto, Harumichi Nishimura, Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications, in Proceedings of 48th International Symposium on Mathematical Foundations of Computer Science (MFCS2023), Leibniz International Proceedings in Informatics 272, pp.63:1-63:15 (2023).
• Francois Le Gall, Masayuki Miyamoto, Harumichi Nishimura, Distributed Quantum Interactive Proofs, in Proceedings of 40th International Symposium on Theoretical Aspects of Computer Science (STACS2023), Leibniz International Proceedings in Informatics 254, pp.42:1-42:21 (2023).
• Akinori Kawachi, Harumichi Nishimura, Communication Complexity of Private Simultaneous Quantum Messages Protocols, in Proceedings of 2nd Conference on Information-Theoretic Cryptography (ITC2021), Leibniz International Proceedings in Informatics 199, pp.20:1-20:19 (2021).
• Francois Le Gall, Harumichi Nishimura, Azur Yakaryilmaz, Quantum Logarithmic Space and Post-Selection, in Proceedings of 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC2021), Leibniz International Proceedings in Informatics 197, pp.10:1-10:17 (2021).
• Pierre Fraigniaud, Francois Le Gall, Harumichi Nishimura, Ami Paz, Distributed Quantum Proofs for Replicated Data, in Proceedings of 12th Innovations in Theoretical Computer Science Conference (ITCS2021), Leibniz International Proceedings in Informatics 185, pp.28:1-28:20 (2021).
• Tomoyuki Morimae, Harumichi Nishimura, Rational proofs for quantum computing, Quantum Information & Computation 20(3-4), pp.181-193 (2020).
• Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi, Seiichiro Tani, Impossibility of blind quantum sampling for classical client, Quantum Information & Computation 19(9-10), pp.793-806 (2019).
• Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura, Generalized Quantum Arthur-Merlin Games, SIAM Journal on Computing 48(3), pp.865-902 (2019).
• Francois Le Gall, Harumichi Nishimura, Ansis Rosmanis, Quantum Advantage for the LOCAL Model in Distributed Computing, in Proceedings of 36th International Symposium on Theoretical Aspects of Computer Science (STACS2019), Leibniz International Proceedings in Informatics 126, pp.49:1-49:14 (2019).
• Tomoyuki Morimae, Yuki Takeuchi, Harumichi Nishimura, Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy, Quantum 2, Article no.106 (2018).
• Francois Le Gall, Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi, Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups, in Proceedings of 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS2018), Leibniz International Proceedings in Informatics 117, pp.26:1-26:13 (2018).
• Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani, Impossibility of classically simulating one-clean-qubit model with multiplicative error, Physical Review Letters 120, Article no.200502 (2018).
• Tomoyuki Morimae, Harumichi Nishimura, Merlinization of complexity classes above BQP, Quantum Information & Computation 17(11-12), pp.959-972 (2017).
• Francois Le Gall, Harumichi Nishimura, Quantum algorithms for matrix products over semirings, Chicago Journal of Theoretical Computer Science 2017, Article 1 (2017).
• Tomoyuki Morimae, Keisuke Fujii, Harumichi Nishimura, Power of one nonclean qubit, Physical Review A 95, Article no.042336 (2017).
• Tomoyuki Morimae, Harumichi Nishimura, Francois Le Gall, Modified group non-membership is in promise-AWPP relative to group oracles, Quantum Information & Computation 17(3-4), pp.242-250 (2017).
• Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita, Quantum query complexity of almost all functions with fixed on-set size, Computational Complexity 25(4), pp.723-734 (2016).
• Tomoyuki Morimae, Harumichi Nishimura, Quantum interpretations of AWPP and APP, Quantum Information & Computation 16(5-6), pp.498-514 (2016).
• Francois Le Gall, Harumichi Nishimura, Seiichiro Tani, Quantum algorithms for finding constant-sized sub-hypergraphs, Theoretical Computer Science 609, pp.569-582 (2016).
• Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, Harumichi Nishimura, Space-efficient error reduction for unitary quantum computations, in Proceedings of 43rd International Colloquium on Automata, Languages, and Programming (ICALP2016), Leibniz International Proceedings in Informatics 55, pp.14:1-14:14 (2016).
• Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani, Power of quantum computation with few clean qubits, in Proceedings of 43rd International Colloquium on Automata, Languages, and Programming (ICALP2016), Leibniz International Proceedings in Informatics 55, pp.13:1-13:14 (2016).
• Tomoyuki Morimae, Masahito Hayashi, Harumichi Nishimura, Keisuke Fujii, Quantum Merlin-Arthur with Clifford Arthur, Quantum Information & Computation 15(15-16), pp.1420-1430 (2015).
• Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura, Generalized Quantum Arthur-Merlin Games, in Proceedings of 30th Conference on Computational Complexity (CCC2015), Leibniz International Proceedings in Informatics 33, pp.488-511 (2015).
• Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura, Stronger methods of making quantum interactive proofs perfectly complete, SIAM Journal on Computing 44(2), pp.243-289 (2015).
• Harumichi Nishimura, Tomoyuki Yamakami, Interactive proofs with quantum finite automata, Theoretical Computer Science 568, pp.1-18 (2015).
• Harumichi Nishimura, Quantum network coding and the current status of its studies, in Proceedings of 2014 International Symposium on Information Theory and its Applications (ISITA2014), pp.331-334 (2014). The preprint version is here.
• Francois Le Gall, Harumichi Nishimura, Seiichiro Tani, Quantum algorithms for finding constant-sized sub-hypergraphs, in Proceedings of 20th International Conference on Computing and Combinatorics (COCOON2014), Lecture Notes in Computer Science 8591, pp.429-440 (2014).
• Francois Le Gall, Harumichi Nishimura, Quantum algorithms for matrix products over semirings, in Proceedings of 14th Scandinavian Symposium and Workshops (SWAT2014), Lecture Notes in Computer Science 8503, pp.331-343 (2014).
• Kazuo Iwama, Harumichi Nishimura, Recovering strings in oracles: quantum and classic, International Journal of Foundations of Computer Science 24(7), pp.979-994 (2013).
• Harumichi Nishimura, Quantum network coding - How can network coding be applied to quantum information?, presented at 2013 IEEE International Symposium on Network Coding (NetCod2013), Jun. 2013. The preprint version is here.
• Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura, Stronger methods of making quantum interactive proofs perfectly complete, in Proceedings of 4th ACM Conference on Innovations in Theoretical Computer Science (ITCS2013), pp.329-352 (2013).
• Richard Cleve, Kazuo Iwama, Francois Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, Shigeru Yamashita, Reconstructing strings from substrings with quantum queries, in Proceedings of 13th Scandinavian Symposium and Workshops (SWAT2012), Lecture Notes in Computer Science 7357, pp.622-633 (2012).
• Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Junichi Teruyama, Quantum counterfeit coin problems, Theoretical Computer Science 456, pp.51-64 (2012).
• Francois Le Gall, Shota Nakagawa, Harumichi Nishimura, On QMA protocols with two short quantum proofs, Quantum Information & Computation 12(7-8), pp.589-600 (2012).
• Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami, Computational indistinguishability between quantum states and its cryptographic application, Journal of Cryptology 25(3), pp.528-555 (2012).
• Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, Harumichi Nishimura, Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems, Quantum Information & Computation 12(5-6), pp.461-471 (2012).
• Ashley Montanaro, Harumichi Nishimura, Rudy Raymond, Unbounded-error quantum query complexity, Theoretical Computer Science 412(35), pp.4619-4628 (2011).
• Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura, Martin Roetteler, Constructing quantum network coding schemes from classical nonlinear protocols, in Proceedings of IEEE International Symposium on Information Theory 2011 (ISIT2011), pp.109-113 (2011).
• Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Junichi Teruyama, Quantum counterfeit coin problems, in Proceedings of 21st International Symposium on Algorithms and Computation (ISAAC2010), Lecture Notes in Computer Science 6506, pp.73-84 (2010).
• Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura, Martin Rotteler, Perfect quantum network communication protocol based on classical network coding, in Proceedings of IEEE International Symposium on Information Theory 2010 (ISIT2010), pp.2686-2690 (2010).
• Harumichi Nishimura, Tomoyuki Yamakami, An application of quantum finite automata to interactive proof systems, Journal of Computer and System Sciences 75(4), pp.255-269 (2009).
• Harumichi Nishimura, Rudy Raymond, Quantum random access coding, IEICE Transactions 92-A(5), pp.1268-1275 (2009).
• Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura, Martin Rotteler, General scheme for perfect quantum network coding with free classical communication, in Proceedings of 36th International Colloquium on Automata, Languages and Programming (ICALP2009), Lecture Notes in Computer Science 5555, pp.622-633 (2009).
• Harumichi Nishimura, Masanao Ozawa, Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families, Quantum Information Processing 8(1), pp.13-24 (2009).
• Masaru Kada, Harumichi Nishimura, Tomoyuki Yamakami, The efficiency of quantum identity testing of multiple states, Journal of Physics A: Mathematical and Theoretical 41, Article no.395309 (2008).
• Ashley Montanaro, Harumichi Nishimura, Rudy Raymond, Unbounded-error quantum query complexity, in Proceedings of 19th International Symposium on Algorithms and Computation (ISAAC2008), Lecture Notes in Computer Science 5369, pp.919-930 (2008).
• Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita, Quantum query complexity of Boolean functions with small on-sets, in Proceedings of 19th International Symposium on Algorithms and Computation (ISAAC2008), Lecture Notes in Computer Science 5369, pp.907-918 (2008).
• Kazuo Iwama, Harumichi Nishimura, Mike Paterson, Rudy Raymond, Shigeru Yamashita, Polynomial-time construction of linear network coding, in Proceedings of 35th International Colloquium on Automata, Languages and Programming (ICALP2008), Lecture Notes in Computer Science 5125, pp.271-282 (2008).
• Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita, Unbounded-error classical and quantum communication complexity, in Proceedings of 18th International Symposium on Algorithms and Computation (ISAAC2007), Lecture Notes in Computer Science 4835, pp.100-111 (2007).
• Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita, Unbounded-error one-way classical and quantum communication complexity, in Proceedings of 34th International Colloquium on Automata, Languages and Programming (ICALP2007), Lecture Notes in Computer Science 4596, pp.110-121 (2007).
• Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita, Quantum network coding, in Proceedings of 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS2007), Lecture Notes in Computer Science 4393, pp.610-621 (2007).
• Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita, (4,1)-quantum random access coding does not exist, in Proceedings of IEEE International Symposium on Information Theory 2006 (ISIT2006), pp.446-450 (2006).
• Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita, (4,1)-quantum random access coding does not exist -one qubit is not enough to recover one of four bits, New Journal of Physics 8, Article no.129 (2006).
• Harumichi Nishimura, Quantum computation with supplementary information, IPSJ Journal 46(10), pp.2392-2399 (2005). IPSJ Digital Courier 1, pp.407-414 (2005).
• Harumichi Nishimura, Masanao Ozawa, Uniformity of quantum circuit families for error-free algorithms, Theoretical Computer Science 332(1-3), pp.487-496 (2005).
• Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami, Computational indistinguishability between quantum states and its cryptographic application, in Proceedings of 24th International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT2005), Lecture Notes in Computer Science 3494, pp.268-284 (2005).
• Harumichi Nishimura, Tomoyuki Yamakami, An application of quantum finite automata to interactive proof systems, in Proceedings of 9th International Conference on Implementation and Application of Automata (CIAA2004), Lecture Notes in Computer Science 3317, pp.225-236 (2005).
• Harumichi Nishimura, Tomoyuki Yamakami, An algorithmic argument for nonadaptive query complexity lower bounds of advised quantum computation, in Proceedings of 29th International Symposium on Mathematical Foundations of Computer Science (MFCS2004), Lecture Notes in Computer Science 3153, pp.827-838 (2004).
• Harumichi Nishimura, Tomoyuki Yamakami, Polynomial-time quantum computation with advice, Information Processing Letters 90(4), pp.195-204 (2004).
• Harumichi Nishimura, Quantum computation with restricted amplitudes, International Journal of Foundations of Computer Science 14(5), pp.853-870 (2003).
• Elham Kashefi, Harumichi Nishimura, Vlatko Vedral, On quantum one-way permutations, Quantum Information and Computation 2(5), pp.379-398 (2002).
• Harumichi Nishimura, Masanao Ozawa, Computational complexity of uniform quantum circuit families and quantum Turing machines, Theoretical Computer Science 276(1-2), pp.147-181 (2002).
• Harumichi Nishimura, On quantum computation with some restricted amplitudes, in Proceedings of 19th Annual Symposium on Theoretical Aspects of Computer Science (STACS2002), Lecture Notes in Computer Science 2285, pp.311-322 (2002).
• Masanao Ozawa, Harumichi Nishimura, Local transition functions of quantum Turing machines, RAIRO Theoretical Informatics and Applications 34(5), pp.379-402 (2000).

International Conference (without Proceedings/with Brief Announcement or Exetnded Abstract)

• Atsuya Hasegawa, Srijita Kundu, Harumichi Nishimura, On the Power of Quantum Distributed Proofs, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC2024), Sep. 2024.
• Francois Le Gall, Masayuki Miyamoto, Harumichi Nishimura, Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC2023), Jul. 2023.
• Francois Le Gall, Masayuki Miyamoto, Harumichi Nishimura, Brief Announcement: Distributed Quantum Interactive Proofs, in Proceedings of 36th International Symposium on Distributed Computing (DISC2022), Leibniz International Proceedings in Informatics 246, pp.48:1-48:3 (2022).
• Harumichi Nishimura, Power of Distributed Quantum Merlin-Arthur Proofs, SUSTech-Nagoya Workshop on Quantum Science 2022, Jun. 2022.
• Harumichi Nishimura, Simultaneous Message Passing Models and Private Simultaneous Messages Protocols with Shared Entanglement, 3rd Workshop on Quantum and Classical Cryogenic Devices, Circuits, and Systems (QCCC2021), Nov. 2021.
• Harumichi Nishimura, SMP model, PSM protocols, and their quantum analogues, SUSTech-Nagoya Workshop on Quantum Science 2021, Jun. 2021.
• Pierre Fraigniaud, Francois Le Gall, Harumichi Nishimura, Ami Paz, Distributed Quantum Proofs for Replicated Data, 24th Workshop on Quantum Information Processing (QIP2021), Feb. 2021.
• Harumichi Nishimura, SWAP Test and Its Applications to Quantum Distributed Computing, 2nd Workshop on Quantum and Classical Cryogenic Devices, Circuits, and Systems (QCCC2020), Dec. 2020.
• Pierre Fraigniaud, Francois Le Gall, Harumichi Nishimura, Ami Paz, Brief Announcement: Distributed Quantum Proofs for Replicated Data, in Proceedings of 34th International Symposium on Distributed Computing (DISC2020), Leibniz International Proceedings in Informatics 179, pp.43:1-43:3 (2020).
• Harumichi Nishimura, More approarches for studying classical verification of quantum computation, 1st Workshop on Quantum and Classical Cryogenic Devices, Circuits, and Systems (QCCC2019), Nov. 2019.
• Harumichi Nishimura, Classical verification for quantum computation, Workshop on Quantum Protocols, Aug. 2019.
• Francois Le Gall, Harumichi Nishimura, Ansis Rosmanis, Quantum Advantage for the LOCAL Model in Distributed Computing, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC2019), Jun. 2019.
• Harumichi Nishimura, Possibility of classical verification for quantum computation, Nagoya-SUSTech Quantum Information Workshop, Apr. 2019.
• Francois Le Gall, Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi, Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups, 18th Asian Quantum Information Science Conference (AQIS2018), Sep. 2018.
• Tomoyuki Morimae, Harumichi Nishimura, Rational proofs for quantum computing, 18th Asian Quantum Information Science Conference (AQIS2018), Sep. 2018.
• Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, Harumichi Nishimura, Space-efficient error reduction for unitary quantum computations, 16th Asian Quantum Information Science Conference (AQIS2016), Aug. 2016.
• Harumichi Nishimura, Power of quantum computation with few clean qubits, Workshop around BQP, Dec. 2015.
• Harumichi Nishimura, Generalized quantum Arthur-Merlin games, Australia-Japan Workshop on Multi-user Quantum Network, Oct. 2014.
• Harumichi Nishimura, Generalized quantum Arthur-Merlin games, ELC Workshop at the University of Tokyo on Quantum Complexity Theory, Aug. 2014.
• Harumichi Nishimura, Quantum Arthur and quantum Merlin, 5th Nagoya Winter Workshop on Quantum Information, Measurement, and Foundations (NWW2014), Mar. 2014.
• Stephen P. Jordan, Hirotada Kobayashi, Francois Le Gall, Daniel Nagaj, Harumichi Nishimura, Towards perfect completeness in QMA, 16th Workshop on Quantum Information Processing (QIP2013), Jan. 2013.
• Harumichi Nishimura, Reducing error probabilities of quantum Merlin-Arthur proof systems, Japan-Singapole Workshop on Multi-user Quantum Networks, Sep. 2012.
• Richard Cleve, Kazuo Iwama, Francois Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, Shigeru Yamashita, Improved quantum algorithms for reconstructing strings from substrings, 5th Annual Meeting of the Asian Association for Algorithms and Computation (AAAC2012), Apr. 2012.
• Richard Cleve, Kazuo Iwama, Francois Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, Shigeru Yamashita, Reconstructing strings from substrings with quantum queries, 4th Annual Meeting of the Asian Association for Algorithms and Computation (AAAC2011), Apr. 2011.
• Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura, Martin Roetteler, Constructing quantum network coding schemes from classical nonlinear protocols, 14th Workshop on Quantum Information Processing (QIP2011), Jan. 2011.
• Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Junichi Teruyama, Quantum counterfeit coin problems, 3rd Annual Meeting of the Asian Association for Algorithms and Computation (AAAC2010), Apr. 2010.
• Harumichi Nishimura, Worst-case winning probabilities for the sum of CHSH games, International Conference on Quantum Information and Technology 2009 (ICQIT2009), Dec. 2009.
• Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita, Unbounded-error classical and quantum communication complexity, 11th Workshop on Quantum Information Processing (QIP2008), Dec. 2007.
• Harumichi Nishimura, Quantum random access coding and its application, 1st Workshop on the Theory on Quantum Computation, Communication and Cryptography (TQC2006), Feb. 2006.
• Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita, Quantum network coding, 9th Workshop on Quantum Information Processing (QIP2006), Jan. 2006.
• Harumichi Nishimura, Tomoyuki Yamakami, Quantum minimal one-way information: relative hardness and quantum advantages of combinatorial tasks, 5th ERATO conference on Quantum Information Science (EQIS2005), Aug. 2005.
• Harumichi Nishimura, Quantum simultaneous protocol with prior entanglement, 4th ERATO conference on Quantum Information Science (EQIS2004), Sep. 2004.
• Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami, A quantum trapdoor one-way function that relies on the hardness of the graph automorphism problem, 3rd ERATO Quantum Information Science Workshop (EQIS2003), Sep. 2003.
• Elham Kashefi, Harumichi Nishimura, Vlatko Vedral, A note on quantum one-way permutations, 10th JST International Symposium on Quantum Computing, Mar. 2002.
• Harumichi Nishimura, On quantum computation with some restricted amplitudes, 1st ERATO Quantum Information Science Workshop (EQIS2001), Sep. 2001.

Misc

• Harumichi Nishimura, Computational complexity of quantum NP and quantum AM, in Proceedings of 33rd Quantum Information Technology Symposium (QIT33), pp.47-51 (Japanese), 2015.
• Shota Nakagawa, Harumichi Nishimura, On the soundness of the Blier-Tapp QMA protocol, in Proceedings of 23rd Quantum Information Technology Symposium (QIT23), pp.132-135 (Japanese), 2010.
• Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita, Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size, arXiv:0908.2468, 2009.
• Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita, Quantum Network Coding for General Graphs, arXiv:quant-ph/0611039, 2006.