79 citations · 380 across the 24 of their papers we have counts for
22 papers · 1 filter
Space-Efficient Error Reduction for Unitary Quantum Computations
Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin +2
This paper develops general space-efficient methods for error reduction for unitary quantum computation. Consider a polynomial-time quantum computation with completeness and so…
Power of Quantum Computation with Few Clean Qubits
Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae +3
This paper investigates the power of polynomial-time quantum computation in which only a very limited number of qubits are initially clean in the |0> state, and all the remaining q…
Impossibility of Classically Simulating One-Clean-Qubit Computation
Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae +3
Deterministic quantum computation with one quantum bit (DQC1) is a restricted model of quantum computing where the input state is the completely mixed state except for a single cle…
Generalized Quantum Arthur-Merlin Games
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
This paper investigates the role of interaction and coins in public-coin quantum interactive proof systems (also called quantum Arthur-Merlin games). While prior works focused on c…
Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
Hirotada Kobayashi, François Le Gall, Harumichi Nishimura
This paper presents stronger methods of achieving perfect completeness in quantum interactive proofs. First, it is proved that any problem in QMA has a two-message quantum interact…
Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems
Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj +1
This paper proves that classical-witness quantum Merlin-Arthur proof systems can achieve perfect completeness. That is, QCMA = QCMA1. This holds under any gate set with which the H…