論文 - 西村　治道

A Survey: SWAP Test and Its Applications to Quantum Complexity Theory

Harumichi Nishimura

Algorithmic Foundations for Social Advancement     頁： 243 - 261   2025年3月

Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries 査読有り 国際共著

Francois Le Gall, Oran Nadler, Harumichi Nishimura, Rotem Oshman

Leibniz International Proceedings in Informatics   324 巻   頁： 34:1 - 34:20   2024年12月

On the Power of Quantum Distributed Proofs 査読有り 国際共著

Atsuya Hasegawa, Srijita Kundu, Harumichi Nishimura

Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing     頁： 220 - 230   2024年6月

Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications 査読有り

Francois Le Gall, Masayuki Miyamoto, Harumichi Nishimura

Leibniz International Proceedings in Informatics     2023年8月

Distributed Quantum Interactive Proofs 査読有り

Francois Le Gall, Masayuki Miyamoto, Harumichi Nishimura

Leibniz International Proceedings in Informatics   254 巻   頁： 42:1 - 42:21   2023年3月

　詳細を見る

記述言語：英語  

Brief Announcement: Distributed Quantum Interactive Proofs 査読有り

Francois Le Gall, Masayuki Miyamoto, Harumichi Nishimura

Leibniz International Proceedings in Informatics   246 巻   2022年10月

Communication Complexity of Private Simultaneous Quantum Messages Protocols 査読有り

Akinori Kawachi, Harumichi Nishimura

Leibniz International Proceedings in Informatics   199 巻   2021年7月

　詳細を見る

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Quantum logarithmic space and post-selection 査読有り 国際共著

Francois Le Gall, Harumichi Nishimura, Abuzer Yakaryilmaz

Leibniz International Proceedings in Informatics   197 巻   2021年7月

　詳細を見る

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

Distributed quantum proofs for replicated data 査読有り 国際共著

Pierre Fraigniaud, Francois Le Gall, Harumichi Nishimura, Ami Paz

Leibniz International Proceedings in Informatics   185 巻   頁： 28:1 - 28:20   2021年1月

Brief Announcement: Distributed quantum proofs for replicated data 査読有り 国際共著

Pierre Fraigniaud, Francois Le Gall, Harumichi Nishimura, Ami Paz

Leibniz International Proceedings in Informatics   179 巻   頁： 43:1 - 43:3   2020年10月

　詳細を見る

掲載種別：研究論文（国際会議プロシーディングス）  

Rational proofs for quantum computing 査読有り

Tomoyuki Morimae, Harumichi Nishimura

Quantum Information and Computation   20 巻   頁： 181-193   2020年4月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Impossibility of blind quantum sampling for classical client 査読有り

Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi, Seiichiro Tani

Quantum Information and Computation   19 巻   頁： 793-806   2019年8月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Quantum Arthur-Merlin Games 査読有り

Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura

SIAM Journal on Computing   48 巻   頁： 865-902   2019年5月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1137/17M1160173

Quantum advantage for the LOCAL model in distributed computing 査読有り

Francois Le Gall, Harumichi Nishimura, Ansis Rosmanis

Leibniz International Proceedings in Informatics   126 巻   頁： 49:1-49:14   2019年3月

　詳細を見る

記述言語：英語  

DOI： 10.4230/LIPIcs.STACS.2019.49

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

Tomoyuki Morimae, Yuki Takeuchi, Harumichi Nishimura

Quantum   2 巻   2018年11月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.22331/q-2018-11-15-106

Impossibility of classically simulating one-clean-qubit model with multiplicative error

Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani

Physical Review Letters   120 巻   2018年5月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1103/PhysRevLett.120.200502

Merlinization of complexity classes above BQP 査読有り

Tomoyuki Morimae, Harumichi Nishimura

Quantum Information and Computation   17 巻 ( 11-12 ) 頁： 0959-0972   2017年9月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Quantum algorithms for matrix products over semirings 査読有り

Francois Le Gall, Harumichi Nishimura

Chicago Journal of Theoretical Computer Science   2017 巻   2017年5月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.4086/cjtcs.2017.001

Power of one nonclean qubit 査読有り

Tomoyuki Morimae, Keisuke Fujii, Harumichi Nishimura

Physical Review A   95 巻   2017年4月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1103/PhysRevA.95.042336

Modified group non-membership is in promise-AWPP relative to group oracles 査読有り

Tomoyuki Morimae, Harumichi Nishimura, Francois Le Gall

Quantum Information and Computation   17 巻 ( 3-4 ) 頁： 242-250   2017年3月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Quantum query complexity of almost all functions with fixed on-set size 査読有り

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita

Computational Complexity   25 巻 ( 4 ) 頁： 723-735   2016年12月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s00037-016-0139-6

Space-Efficient Error Reduction for Unitary Quantum Computations 査読有り

Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, Harumichi Nishimura

Leibniz International Proceedings in Informatics   55 巻   頁： 14:1-14:14   2016年7月

　詳細を見る

記述言語：英語  

DOI： 10.4230/LIPIcs.ICALP.2016.14

Power of quantum computation with few clean qubits 査読有り

Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani

Leibniz International Proceedings in Informatics   55 巻   頁： 13:1-13:14   2016年7月

　詳細を見る

記述言語：英語  

DOI： 10.4230/LIPIcs.ICALP.2016.13

Quantum interpretations of AWPP and APP 査読有り

Tomoyuki Morimae, Harumichi Nishimura

Quantum Information and Computation   16 巻 ( 5-6 ) 頁： 498-514   2016年4月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Quantum algorithms for finding constant-sized sub-hypergraphs 査読有り

Francois Le Gall, Harumichi Nishimura, Seiichiro Tani

Theoretical Computer Science   609 巻 ( 3 ) 頁： 569-582   2016年1月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2015.10.006

Quantum Merlin-Arthur with Clifford Arthur

Tomoyuki Morimae, Masahito Hayashi, Harumichi Nishimura, Keisuke Fujii

Quantum Information and Computation   15 巻 ( 15-16 ) 頁： 1420-1430   2015年11月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Generalized quantum Arthur-Merlin games 査読有り

Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura

Leibniz International Proceedings in Informatics   33 巻   頁： 488-511   2015年6月

　詳細を見る

記述言語：英語  

DOI： 10.4230/LIPIcs.CCC.2015.488

Stronger methods of making quantum interactive proofs perfectly complete 査読有り

Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura

SIAM Journal on Computing   44 巻 ( 2 ) 頁： 243-289   2015年3月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1137/140971944

Interactive proofs with quantum finite automata 査読有り

Harumichi Nishimura, Tomoyuki Yamakami

Theoretical Computer Science   568 巻   頁： 1-18   2015年2月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2014.11.030

Quantum network coding and the current status of its studies 招待有り

Harumichi Nishimura

Proceedings of the International Symposium on Information Theory and Its Applications (ISITA2014)     頁： 331-334   2014年10月

　詳細を見る

記述言語：英語  

Quantum algorithms for finding constant-sized subgraphs

Francois Le Gall, Harumichi Nishimura, Seiichiro Tani

Lecture Notes in Computer Science (Proceedings of 20th International Conference on Computing and Combinatorics)   8591 巻   頁： 429-440   2014年8月

　詳細を見る

記述言語：英語  

DOI： 10.1007/978-3-319-08783-2_37

Quantum algorithms for matrix product over semirings

Francois Le Gall, Harumichi Nishimura

Lecture Notes in Computer Science (Proceedings of 14th Scandinavian Symposium and Workshops)   8503 巻   頁： 331-343   2014年7月

　詳細を見る

記述言語：英語  

DOI： 10.1007/978-3-319-08404-6_29

RECOVERING STRINGS IN ORACLES: QUANTUM AND CLASSIC 招待有り

Kazuo Iwama, Harumichi Nishimura

International Journal of Foundations of Computer Science   24 巻 ( 7 ) 頁： 979-993   2013年11月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1142/S0129054113400261

Quantum network coding - How can network coding be applied to quantum information? 招待有り

Harumichi Nishimura

Proceedings of the 2013 IEEE International Symposium on Network Coding     2013年6月

　詳細を見る

記述言語：英語  

DOI： 10.1109/NetCod.2013.6570840

Stronger methods of making quantum interactive proofs perfectly complete 査読有り

Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura

Proceedings of the 4th ACM Conference on Innovations in Theoretical Computer Science Conference (ITCS2013)     頁： 329-352   2013年1月

　詳細を見る

記述言語：英語  

DOI： 10.1145/2422436.2422475

Quantum counterfeit coin problems

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Junichi Teruyama

Theoretical Computer Science   456 巻   頁： 51-64   2012年8月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2012.05.039

On QMA protocols with two short quantum proofs

Francois Le Gall, Shota Nakagawa, Harumichi Nishimura

Quantum Information & Computation   12 巻   頁： 589-600   2012年8月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Reconstructing strings from substrings with quantum queries

Richard Cleve, Kazuo Iwama, Francois Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, Shigeru Yamashita

Lecture Notes in Computer Science (Proceedings of 13th Scandinavian Symposium and Workshops)   7357 巻   頁： 622-633   2012年7月

　詳細を見る

記述言語：英語  

DOI： 10.1007/978-3-642-31155-0_34

Computational indistinguishability between quantum states and its cryptographic application

Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami

Journal of Cryptology   25 巻   頁： 528-555   2012年7月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s00145-011-9103-4

Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems

Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, Harumichi Nishimura

Quantum Information & Computation   12 巻   頁： 461-471   2012年6月

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Unbounded-error quantum query complexity

Ashley Montanaro, Harumichi Nishimura, Rudy Raymond

Theoretical Computer Science   412 巻   頁： 4619-4628   2011年

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2011.04.043

Constructing quantum network coding schemes from classical nonlinear protocols

Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura, Martin Roetteler

Proceedings of IEEE International Symposium on Information Theory 2011     頁： 109-113   2011年

　詳細を見る

記述言語：英語  

DOI： 10.1109/ISIT.2011.6033701

Quantum counterfeit coin problems

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Junichi Teruyama

Lecture Notes in Computer Science (Proceedings of 21st International Symposium on Algorithms and Computation)   6506 巻   頁： 73-84   2010年

　詳細を見る

記述言語：英語  

DOI： 10.1007/978-3-642-17517-6_10

Perfect quantum network communication protocol based on classical network coding

Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura, Martin Roetteler

Proceedings of IEEE International Symposium on Information Theory 2010     頁： 2686-2690   2010年

　詳細を見る

記述言語：英語  

DOI： 10.1109/ISIT.2010.5513644

An application of quantum finite automata to interactive proof systems

Harumichi Nishimura, Tomoyuki Yamakami

Journal of Computer and System Sciences   75 巻   頁： 255-269   2009年

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.jcss.2008.12.001

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

Harumichi Nishimura, Masanao Ozawa

Quantum Information Processing   8 巻   頁： 13-24   2009年

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1007/s11128-008-0091-8

Quantum random access coding 招待有り

Harumichi Nishimura, Rudy Raymond

IEICE Transactions   92 巻 ( A(5) ) 頁： 1268-1275   2009年

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

General scheme for perfect quantum network coding with free classical communication

Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura, Martin Roetteler

Lecture Notes in Computer Science (Proceedings of 36th International Colloquium on Automata, Languages and Programming)   5555 巻   頁： 622-633   2009年

　詳細を見る

記述言語：英語  

DOI： 10.1007/978-3-642-02927-1_52

Unbounded-error quantum query complexity

Ashley Montanaro, Harumichi Nishimura, Rudy Raymond

Lecture Notes in Computer Science (Proceedings of 19th International Symposium on Algorithms and Computation)   5369 巻   頁： 919-930   2008年

　詳細を見る

記述言語：英語  

DOI： 10.1007/978-3-540-92182-0_80

Polynomial-time construction of linear network coding

Kazuo Iwama, Harumichi Nishimura, Mike Paterson, Rudy Raymond, Shigeru Yamashita

Lecture Notes in Computer Science (Proceedings of 35th International Colloquium on Automata, Languages and Programming)   5125 巻   頁： 271-282   2008年

　詳細を見る

記述言語：英語  

DOI： 10.1007/978-3-540-70575-8_23

The efficiency of quantum identity testing of multiple states

Masaru Kada, Harumichi Nishimura, Tomoyuki Yamakami

Journal of Physics A: Mathematical and Theoretical   41 巻 ( Article no. 395309 ) 頁： 1-13   2008年

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1088/1751-8113/41/39/395309

Quantum query complexity of Boolean functions with small on-sets

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita

Lecture Notes in Computer Science (Proceedings of 19th International Symposium on Algorithms and Computation)   5369 巻   頁： 907-918   2008年

　詳細を見る

記述言語：英語  

DOI： 10.1007/978-3-540-92182-0_79

Unbounded-error classical and quantum communication complexity

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita

Lecture Notes in Computer Science (Proceedings of 18th International Symposium on Algorithms and Computation)   4835 巻   頁： 100-111   2007年

　詳細を見る

記述言語：英語  

DOI： 10.1007/978-3-540-77120-3_11

Unbounded-error one-way classical and quantum communication complexity

Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita

Lecture Notes in Computer Science (Proceedings of 34th International Colloquium on Automata, Languages and Programming)   4596 巻   頁： 110-121   2007年

　詳細を見る

記述言語：英語  

DOI： 10.1007/978-3-540-73420-8_12

Quantum network coding

Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita

Lecture Notes in Computer Science (Proceedings of 24th Annual Symposium on Theoretical Aspects of Computer Science)   4393 巻   頁： 610-621   2007年

　詳細を見る

記述言語：英語  

DOI： 10.1007/978-3-540-70918-3_52

(4,1)-quantum random access coding does not exist - one qubit is not enough to recover one of four bits

Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita

New Journal of Physics   8 巻 ( Article no. 129 ) 頁： 1-11   2006年

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1088/1367-2630/8/8/129

Quantum computation with supplementary information 招待有り

Harumichi Nishimura

IPSJ Journal   46 巻   頁： 2392-2399   2005年

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.2197/ipsjdc.1.407

Uniformity of quantum circuit families for error-free algorithms

Harumichi Nishimura, Masanao Ozawa

Theoretical Computer Science   332 巻   頁： 487-496   2005年

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.tcs.2004.12.020

Polynomial-time quantum computation with advice

Harumichi Nishimura, Tomoyuki Yamakami

Information Processing Letters   90 巻   頁： 195-204   2004年

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/j.ipl.2004.02.005

An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation 査読有り

Harumichi Nishimura, Tomoyuki Yamakami

Lecture Notes in Computer Science (Proceedings of the 29th International Symposium on Mathematical Foundations of Computer Science)   3153 巻   頁： 827-838   2004年

　詳細を見る

記述言語：英語  

DOI： 10.1007/978-3-540-28629-5_65

Quantum Computation With Restricted Amplitudes 査読有り

Harumichi Nishimura

International Journal of Foundations of Computer Science   14 巻   頁： 853-870   2003年

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1142/S0129054103002059

On quantum one-way permutations 査読有り

Elham Kashefi, Harumichi Nishimura, Vlatko Vedral

Quantum Information and Computation   2 巻   頁： 379-398   2002年

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

Computational complexity of uniform quantum circuit families and quantum Turing machines 査読有り

Harumichi Nishimura, Masanao Ozawa

Theoretical Computer Science   276 巻   頁： 147-181   2002年

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1016/S0304-3975(01)00111-6

Local transition functions of quantum Turing machines 査読有り

Masanao Ozawa, Harumichi Nishimura

RAIRO Theoretical Informatics and Applications   34 巻   頁： 379-402   2000年

　詳細を見る

記述言語：英語   掲載種別：研究論文（学術雑誌）  

DOI： 10.1051/ita:2000123