Harumichi Nishimura

111 papers A* 6A 11B 10C 2Misc 1Journal 73Unranked 8
YearRankTypeTitle / Venue / Authors
2025 J jnl
Does there exist a quantum fingerprinting protocol without coherent measurements?
CoRR
Atsuya Hasegawa, Srijita Kundu, François Le Gall, Harumichi Nishimura, Qisheng Wang
2025 A* conf
Group Order is in QCMA.
FOCS
François Le Gall, Harumichi Nishimura, Dhara Thakkar
2025 J jnl
Group Order is in QCMA.
CoRR
François Le Gall, Harumichi Nishimura, Dhara Thakkar
2025 A conf
Space-Bounded Quantum Interactive Proof Systems.
CCC
François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang
2024 A* conf
On the Power of Quantum Distributed Proofs.
PODC
Atsuya Hasegawa, Srijita Kundu, Harumichi Nishimura
2024 J jnl
On the Power of Quantum Distributed Proofs.
CoRR
Atsuya Hasegawa, Srijita Kundu, Harumichi Nishimura
2024 B conf
Quantum Simultaneous Protocols Without Public Coins Using Modified Equality Queries.
OPODIS
François Le Gall, Oran Nadler, Harumichi Nishimura, Rotem Oshman
2024 J jnl
Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries.
CoRR
François Le Gall, Oran Nadler, Harumichi Nishimura, Rotem Oshman
2024 J jnl
Space-bounded quantum interactive proof systems.
CoRR
François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang
2024 J jnl
Space-bounded quantum interactive proof systems.
Electron. Colloquium Comput. Complex.
François Le Gall, Yupan Liu, Harumichi Nishimura, Qisheng Wang
2023 B conf
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications.
MFCS
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
2023 A conf
Distributed Quantum Interactive Proofs.
STACS
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
2022 A conf
Brief Announcement: Distributed Quantum Interactive Proofs.
DISC
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
2022 J jnl
Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications.
CoRR
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
2022 J jnl
Distributed Quantum Interactive Proofs.
CoRR
François Le Gall, Masayuki Miyamoto, Harumichi Nishimura
2021 A conf
Communication Complexity of Private Simultaneous Quantum Messages Protocols.
ITC
Akinori Kawachi, Harumichi Nishimura
2021 J jnl
Communication Complexity of Private Simultaneous Quantum Messages Protocols.
CoRR
Akinori Kawachi, Harumichi Nishimura
2021 J jnl
Communication Complexity of Private simultaneous Quantum Messages Protocols.
IACR Cryptol. ePrint Arch.
Akinori Kawachi, Harumichi Nishimura
2021 A conf
Distributed Quantum Proofs for Replicated Data.
ITCS
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz
2021 — conf
Quantum Logarithmic Space and Post-Selection.
TQC
François Le Gall, Harumichi Nishimura, Abuzer Yakaryilmaz
2021 J jnl
Quantum Logarithmic Space and Post-selection.
CoRR
François Le Gall, Harumichi Nishimura, Abuzer Yakaryilmaz
2020 A conf
Brief Announcement: Distributed Quantum Proofs for Replicated Data.
DISC
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz
2020 J jnl
Distributed Quantum Proofs for Replicated Data.
CoRR
Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz
2020 J jnl
Rational proofs for quantum computing.
Quantum Inf. Comput.
Tomoyuki Morimae, Harumichi Nishimura
2019 J jnl
Generalized Quantum Arthur-Merlin Games.
SIAM J. Comput.
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
2019 J jnl
Impossibility of blind quantum sampling for classical client.
Quantum Inf. Comput.
Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi, Seiichiro Tani
2019 A conf
Quantum Advantage for the LOCAL Model in Distributed Computing.
STACS
François Le Gall, Harumichi Nishimura, Ansis Rosmanis
2018 J jnl
Impossibility of blind quantum sampling for classical client.
CoRR
Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi, Seiichiro Tani
2018 B conf
Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups.
MFCS
François Le Gall, Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi
2018 J jnl
Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups.
CoRR
François Le Gall, Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi
2018 J jnl
Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy.
Quantum
Tomoyuki Morimae, Yuki Takeuchi, Harumichi Nishimura
2018 J jnl
Quantum Advantage for the LOCAL Model in Distributed Computing.
CoRR
François Le Gall, Harumichi Nishimura, Ansis Rosmanis
2018 J jnl
Rational proofs for quantum computing.
CoRR
Tomoyuki Morimae, Harumichi Nishimura
2017 J jnl
Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy.
CoRR
Tomoyuki Morimae, Yuki Takeuchi, Harumichi Nishimura
2017 J jnl
Merlinization of complexity classes above BQP.
CoRR
Tomoyuki Morimae, Harumichi Nishimura
2017 J jnl
Merlinization of complexity classes above BQP.
Quantum Inf. Comput.
Tomoyuki Morimae, Harumichi Nishimura
2017 J jnl
Modified Group Non-Membership is in Promise-AWPP relative to group oracles.
Quantum Inf. Comput.
Tomoyuki Morimae, Harumichi Nishimura, Francois Le Gall
2017 J jnl
Quantum Algorithms for Matrix Products over Semirings.
Chic. J. Theor. Comput. Sci.
François Le Gall, Harumichi Nishimura
2016 J jnl
Modified group non-membership is in AWPP.
CoRR
Tomoyuki Morimae, Harumichi Nishimura, Francois Le Gall
2016 A* conf
Power of Quantum Computation with Few Clean Qubits.
ICALP
Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani
2016 J jnl
Power of one non-clean qubit.
CoRR
Tomoyuki Morimae, Keisuke Fujii, Harumichi Nishimura
2016 J jnl
Quantum Merlin-Arthur with noisy channel.
CoRR
Tomoyuki Morimae, Keisuke Fujii, Harumichi Nishimura
2016 J jnl
Quantum Query Complexity of Almost All Functions with Fixed On-set Size.
Comput. Complex.
Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita
2016 J jnl
Quantum algorithms for finding constant-sized sub-hypergraphs.
Theor. Comput. Sci.
François Le Gall, Harumichi Nishimura, Seiichiro Tani
2016 J jnl
Quantum interpretations of AWPP and APP.
Quantum Inf. Comput.
Tomoyuki Morimae, Harumichi Nishimura
2016 A* conf
Space-Efficient Error Reduction for Unitary Quantum Computations.
ICALP
Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, Harumichi Nishimura
2016 J jnl
Space-Efficient Error Reduction for Unitary Quantum Computations.
CoRR
Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, Harumichi Nishimura
2015 A conf
Generalized Quantum Arthur-Merlin Games.
CCC
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
2015 J jnl
Interactive proofs with quantum finite automata.
Theor. Comput. Sci.
Harumichi Nishimura, Tomoyuki Yamakami
2015 J jnl
Power of Quantum Computation with Few Clean Qubits.
CoRR
Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani
2015 J jnl
Power of quantum computing with restricted postselections.
CoRR
Tomoyuki Morimae, Harumichi Nishimura
2015 J jnl
Quantum Merlin-Arthur with Clifford Arthur.
Quantum Inf. Comput.
Tomoyuki Morimae, Masahito Hayashi, Harumichi Nishimura, Keisuke Fujii
2015 J jnl
Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete.
SIAM J. Comput.
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
2014 J jnl
Impossibility of Classically Simulating One-Clean-Qubit Computation.
CoRR
Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani
2014 J jnl
Interactive Proofs with Quantum Finite Automata.
CoRR
Harumichi Nishimura, Tomoyuki Yamakami
2014 Misc conf
Quantum Algorithms for Finding Constant-Sized Sub-hypergraphs.
COCOON
François Le Gall, Harumichi Nishimura, Seiichiro Tani
2014 — conf
Quantum Algorithms for Matrix Products over Semirings.
SWAT
François Le Gall, Harumichi Nishimura
2014 C conf
Quantum network coding and the current status of its studies.
ISITA
Harumichi Nishimura
2013 J jnl
Generalized Quantum Arthur-Merlin Games.
CoRR
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
2013 J jnl
Quantum Algorithms for Finding Constant-sized Sub-hypergraphs over 3-uniform Hypergraphs.
CoRR
François Le Gall, Harumichi Nishimura, Seiichiro Tani
2013 J jnl
Quantum Algorithms for Matrix Products over Semirings.
CoRR
François Le Gall, Harumichi Nishimura
2013 — conf
Quantum network coding - How can network coding be applied to quantum information?
NetCod
Harumichi Nishimura
2013 J jnl
Recovering Strings in Oracles: Quantum and Classic.
Int. J. Found. Comput. Sci.
Kazuo Iwama, Harumichi Nishimura
2013 A conf
Stronger methods of making quantum interactive proofs perfectly complete.
ITCS
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
2012 J jnl
Achieving perfect completeness in classical-witness quantum merlin-arthur proof systems.
Quantum Inf. Comput.
Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, Harumichi Nishimura
2012 J jnl
Computational Indistinguishability Between Quantum States and Its Cryptographic Application.
J. Cryptol.
Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami
2012 J jnl
On QMA protocols with two short quantum proofs.
Quantum Inf. Comput.
François Le Gall, Shota Nakagawa, Harumichi Nishimura
2012 J jnl
Quantum counterfeit coin problems.
Theor. Comput. Sci.
Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Junichi Teruyama
2012 J jnl
Reconstructing Strings from Substrings with Quantum Queries
CoRR
Richard Cleve, Kazuo Iwama, François Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, Shigeru Yamashita
2012 — conf
Reconstructing Strings from Substrings with Quantum Queries.
SWAT
Richard Cleve, Kazuo Iwama, François Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, Shigeru Yamashita
2012 J jnl
Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
CoRR
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
2011 B conf
Constructing quantum network coding schemes from classical nonlinear protocols.
ISIT
Hirotada Kobayashi, Francois Le Gall, Harumichi Nishimura, Martin Rötteler
2011 J jnl
On QMA Protocols with Two Short Quantum Proofs
CoRR
François Le Gall, Shota Nakagawa, Harumichi Nishimura
2011 J jnl
Unbounded-error quantum query complexity.
Theor. Comput. Sci.
Ashley Montanaro, Harumichi Nishimura, Rudy Raymond
2010 J jnl
Constructing Quantum Network Coding Schemes from Classical Nonlinear Protocols
CoRR
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, Martin Roetteler
2010 B conf
Perfect quantum network communication protocol based on classical network coding.
ISIT
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, Martin Rötteler
2010 J jnl
Quantum Counterfeit Coin Problems
CoRR
Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Junichi Teruyama
2010 — conf
Quantum Counterfeit Coin Problems.
ISAAC (1)
Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Junichi Teruyama
2009 J jnl
An application of quantum finite automata to interactive proof systems.
J. Comput. Syst. Sci.
Harumichi Nishimura, Tomoyuki Yamakami
2009 J jnl
Average/Worst-Case Gap of Quantum Query Complexities by On-Set Size
CoRR
Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita
2009 J jnl
General Scheme for Perfect Quantum Network Coding with Free Classical Communication
CoRR
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, Martin Rötteler
2009 — conf
General Scheme for Perfect Quantum Network Coding with Free Classical Communication.
ICALP (1)
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, Martin Rötteler
2009 J jnl
Perfect Quantum Network Communication Protocol Based on Classical Network Coding
CoRR
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, Martin Rötteler
2009 J jnl
Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families.
Quantum Inf. Process.
Harumichi Nishimura, Masanao Ozawa
2009 J jnl
Quantum Random Access Coding.
IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
Harumichi Nishimura, Rudy Raymond
2008 — conf
Polynomial-Time Construction of Linear Network Coding.
ICALP (1)
Kazuo Iwama, Harumichi Nishimura, Mike Paterson, Rudy Raymond, Shigeru Yamashita
2008 B conf
Quantum Query Complexity of Boolean Functions with Small On-Sets.
ISAAC
Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita
2008 B conf
Unbounded-Error Quantum Query Complexity.
ISAAC
Ashley Montanaro, Harumichi Nishimura, Rudy Raymond
2007 A conf
Quantum Network Coding.
STACS
Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond Harry Putra, Shigeru Yamashita
2007 B conf
Unbounded-Error Classical and Quantum Communication Complexity.
ISAAC
Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita
2007 A* conf
Unbounded-Error One-Way Classical and Quantum Communication Complexity.
ICALP
Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita
2006 B conf
(4, 1)-Quantum Random Access Coding Does Not Exist.
ISIT
Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita
2006 J jnl
Computational Indistinguishability between Quantum States and Its Cryptographic Application.
IACR Cryptol. ePrint Arch.
Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami
2006 J jnl
Quantum Computation with Supplementary Information.
Inf. Media Technol.
Harumichi Nishimura
2006 — conf
Quantum Network Coding.
Complexity of Boolean Functions
Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, Shigeru Yamashita
2005 A* conf
Computational Indistinguishability Between Quantum States and Its Cryptographic Application.
EUROCRYPT
Akinori Kawachi, Takeshi Koshiba, Harumichi Nishimura, Tomoyuki Yamakami
2005 J jnl
Quantum Minimal One Way Information: Relative Hardness and Quantum Advantage of Combinatorial Tasks
CoRR
Harumichi Nishimura, Tomoyuki Yamakami
2005 J jnl
Uniformity of quantum circuit families for error-free algorithms.
Theor. Comput. Sci.
Harumichi Nishimura, Masanao Ozawa
2004 B conf
An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation (Extended Abstract).
MFCS
Harumichi Nishimura, Tomoyuki Yamakami
2004 J jnl
An Application of Quantum Finite Automata to Interactive Proof Systems
CoRR
Harumichi Nishimura, Tomoyuki Yamakami
2004 J jnl
An Application of Quantum Finite Automata to Interactive Proof Systems
Electron. Colloquium Comput. Complex.
Tomoyuki Yamakami, Harumichi Nishimura
2004 C conf
An Application of Quantum Finite Automata to Interactive Proof Systems.
CIAA
Harumichi Nishimura, Tomoyuki Yamakami
2004 J jnl
Polynomial time quantum computation with advice.
Inf. Process. Lett.
Harumichi Nishimura, Tomoyuki Yamakami
2003 J jnl
An Algorithmic Argument for Query Complexity Lower Bounds of Advised Quantum Computation
CoRR
Harumichi Nishimura, Tomoyuki Yamakami
2003 J jnl
Polynomial time quantum computation with advice
CoRR
Harumichi Nishimura, Tomoyuki Yamakami
2003 J jnl
Polynomial time quantum computation with advice
Electron. Colloquium Comput. Complex.
Harumichi Nishimura, Tomoyuki Yamakami
2003 J jnl
Quantum Computation With Restricted Amplitudes.
Int. J. Found. Comput. Sci.
Harumichi Nishimura
2002 J jnl
Computational complexity of uniform quantum circuit families and quantum Turing machines.
Theor. Comput. Sci.
Harumichi Nishimura, Masanao Ozawa
2002 A conf
On Quantum Computation with Some Restricted Amplitudes.
STACS
Harumichi Nishimura
2002 J jnl
On quantum one-way permutations.
Quantum Inf. Comput.
Elham Kashefi, Harumichi Nishimura, Vlatko Vedral
2000 J jnl
Local transition functions of quantum Turing machines.
RAIRO Theor. Informatics Appl.
Masanao Ozawa, Harumichi Nishimura