Tomoyuki Morimae

J-GLOBAL         Last updated: Jun 24, 2019 at 14:12
 
Avatar
Name
Tomoyuki Morimae
Nickname
morimae
Affiliation
Kyoto University
Section
Yukawa Institute for Theoretical Physics
Research funding number
50708302

Research Areas

 
 

Academic & Professional Experience

 
 
   
 
Kyoto University Yukawa Institute for Theoretical Physics
 

Published Papers

 
Tomoyuki Morimae, Suguru Tamaki
   Feb 2019
We first show that under SETH and its variant, strong and weak classical
simulations of quantum computing are impossible in certain double-exponential
time of the circuit depth. We next show that under Orthogonal Vectors, 3-SUM,
and their variants...
Tomoyuki Morimae, Suguru Tamaki
   Jan 2019
It is known that several sub-universal quantum computing models cannot be
classically simulated in polynomial-time unless the polynomial-time hierarchy
collapses. These results, however, do not rule out possibilities of
exponential- or sub-exponen...
Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi, Seiichiro Tani
   Dec 2018
Blind quantum computing enables a client, who can only generate or measure
single-qubit states, to delegate quantum computing to a remote quantum server
in such a way that the input, output, and program are hidden from the server.
It is an open pr...
Yuki Takeuchi, Tomoyuki Morimae, Masahito Hayashi
   Sep 2018
Measurement-based quantum computing is one of the most promising quantum
computing models. Among various universal resource states proposed so far, the
Union Jack state is the best in the sense that it requires only Pauli-Tex, Tex,
and Tex basis m...
Yuki Takeuchi, Atul Mantri, Tomoyuki Morimae, Akihiro Mizutani, Joseph F. Fitzsimons
npj Quantum Information 5, 27 (2019)      Jun 2018
Verifying quantum states is central to certifying the correct operation of
various quantum information processing tasks. In particular, in
measurement-based quantum computing, checking whether correct graph states are
generated is essential for re...
François Le Gall, Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi
   May 2018
In this paper we consider what can be computed by a user interacting with a
potentially malicious server, when the server performs polynomial-time quantum
computation but the user can only perform polynomial-time classical (i.e.,
non-quantum) comp...
Tomoyuki Morimae, Harumichi Nishimura
   Apr 2018
It is an open problem whether a classical client (verifier) can delegate
quantum computing to a remote quantum server (prover) in such a way that the
correctness of quantum computing is somehow guaranteed. We show that such a
delegation is possibl...
Tomoyuki Morimae
   Mar 2018
Blind quantum computing enables a client, who does not have enough quantum
technologies, to delegate her quantum computing to a remote quantum server in
such a way that her privacy is protected against the server. Some blind quantum
computing prot...
Fitzsimons Joseph F., Hajdusek Michal, Morimae Tomoyuki
PHYSICAL REVIEW LETTERS   120(4)    Jan 2018   [Refereed]
Tomoyuki Morimae, Yuki Takeuchi, Harumichi Nishimura
Quantum 2, 106 (2018)      Nov 2017
We introduce a simple sub-universal quantum computing model, which we call
the Hadamard-classical circuit with one-qubit (HC1Q) model. It consists of a
classical reversible circuit sandwiched by two layers of Hadamard gates, and
therefore it is in...
Go Sato, Takeshi Koshiba, Tomoyuki Morimae
   Sep 2017
Blind quantum computation is a two-party protocol which involves a server Bob
who has rich quantum computational resource and provides quantum computation
service and a client Alice who wants to delegate her quantum computation to Bob
without reve...
Yuki Takeuchi, Tomoyuki Morimae
Phys. Rev. X 8, 021060 (2018)      Sep 2017
Verification is a task to check whether a given quantum state is close to an
ideal state or not. In this paper, we show that a variety of many-qubit quantum
states can be verified with only sequential single-qubit measurements of Pauli
operators. ...
Tomoyuki Morimae
Phys. Rev. A 96, 040302(R) (2017)      Apr 2017
The one clean qubit model (or the DQC1 model) is a restricted model of
quantum computing where only a single input qubit is pure and all other input
qubits are maximally mixed. In spite of the severe restriction, the model can
solve several proble...
Tomoyuki Morimae, Harumichi Nishimura
Quantum Information and Computation 17, pp 0959-0972 (2017)      Apr 2017
We study how complexity classes above BQP, such as postBQP, Tex, and SBQP, change if we "Merlinize" them, i.e., if we allow
an extra input quantum state (or classical bit string) given by Merlin as
witness. Main results are th...
Tomoyuki Morimae, Yuki Takeuchi, Masahito Hayashi
Phys. Rev. A 96, 062321 (2017)      Jan 2017
Hypergraph states are generalizations of graph states where controlled-Tex
gates on edges are replaced with generalized controlled-Tex gates on
hyperedges. Hypergraph states have several advantages over graph states. For
example, certain hypergrap...
Tomoyuki Morimae, Keisuke Fujii, Harumichi Nishimura
Phys. Rev. A 95, 042336 (2017)      Oct 2016
The one-clean qubit model (or the DQC1 model) is a restricted model of
quantum computing where only a single qubit of the initial state is pure and
others are maximally mixed. Although the model is not universal, it can
efficiently solve several p...
Morimae Tomoyuki
PHYSICAL REVIEW A   94(4)    Oct 2016   [Refereed]
Tomoyuki Morimae
Phys. Rev. A 96, 052308 (2017)      Sep 2016
Measurement-based quantum computing enables universal quantum computing with
only adaptive single-qubit measurements on certain many-qubit states, such as
the graph state, the Affleck-Kennedy-Lieb-Tasaki (AKLT) state, and several
tensor-network st...
Tomoyuki Morimae, Keisuke Fujii, Harumichi Nishimura
   Aug 2016
What happens if in QMA the quantum channel between Merlin and Arthur is
noisy? It is not difficult to show that such a modification does not change the
computational power as long as the noise is not too strong so that errors are
correctable with ...
Yuki Takeuchi, Keisuke Fujii, Tomoyuki Morimae, Nobuyuki Imoto
   Jul 2016
Verifiable blind quantum computing allows a client with poor quantum devices
to delegate universal quantum computing to a remote quantum server in such a
way that the client's privacy is protected and the honesty of the server is
verified. In exis...
Tomoyuki Morimae
   Jul 2016
We show that the Quantum State Distinguishability (QSD), which is a
QSZK-complete problem, and the Quantum Circuit Distinguishability (QCD), which
is a QIP-complete problem, can be solved by the verifier who can perform only
single-qubit measureme...
Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, Harumichi Nishimura
Proceedings of 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), pp. 14:1-14:14      Apr 2016
This paper develops general space-efficient methods for error reduction for
unitary quantum computation. Consider a polynomial-time quantum computation
with completeness Tex and soundness Tex, either with or without a witness
(corresponding to QMA...
QUANTUM INTERPRETATIONS OF AWPP AND APP
Morimae Tomoyuki, Nishimura Harumichi
QUANTUM INFORMATION & COMPUTATION   16(5-6) 498-514   Apr 2016   [Refereed]
Tomoyuki Morimae, Joseph F. Fitzsimons
   Mar 2016
We propose a simple protocol for the verification of quantum computation
after the computation has been performed. Our construction can be seen as an
improvement on previous results in that it requires only a single prover, who
is restricted to me...
Tomoyuki Morimae
   Feb 2016
We show that the class QAM does not change even if the verifier's ability is
restricted to only single-qubit measurements. To show the result, we use the
idea of the measurement-based quantum computing: the verifier, who can do only
single-qubit m...
Tomoyuki Morimae, Harumichi Nishimura, Francois Le Gall
   Feb 2016
It is known that the group non-membership problem is in QMA relative to any
group oracle and in Tex relative to group oracles for
solvable groups. We consider a modified version of the group non-membership
problem where the or...
Chiara Greganti, Marie-Christine Roehsner, Stefanie Barz, Tomoyuki Morimae, Philip Walther
New J. Phys. 18 013020 (2016)      Jan 2016
Blind quantum computing allows for secure cloud networks of quasi-classical
clients and a fully fledged quantum server. Recently, a new protocol has been
proposed, which requires a client to perform only measurements. We demonstrate
a proof-of-pri...
Tomoyuki Morimae, Daniel Nagaj, Norbert Schuch
Phys. Rev. A 93, 022326 (2016)      Oct 2015
QMA (Quantum Merlin Arthur) is the class of problems which, though
potentially hard to solve, have a quantum solution which can be verified
efficiently using a quantum computer. It thus forms a natural quantum version
of the classical complexity c...
Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani
   Sep 2015
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 qubits are initially in the totally mixed state.
No initializations ...
Tomoyuki Morimae, Masahito Hayashi, Harumichi Nishimura, Keisuke Fujii
Quantum Information and Computation 15, pp1420-1430 (2015)      Jun 2015
We show that the class QMA does not change even if we restrict Arthur's
computing ability to only Clifford gate operations (plus classical XOR gate).
The idea is to use the fact that the preparation of certain single-qubit
states, so called magic ...
Masahito Hayashi, Tomoyuki Morimae
Phys. Rev. Lett. 115, 220502 (2015)      May 2015
We introduce a simple protocol for verifiable measurement-only blind quantum
computing. Alice, a client, can perform only single-qubit measurements, whereas
Bob, a server, can generate and store entangled many-qubit states. Bob
generates copies of...
Tomoyuki Morimae, Harumichi Nishimura
Quantum Information and Computation 16, pp.0498-0514 (2016)      Jan 2015
AWPP is a complexity class introduced by Fenner, Fortnow, Kurtz, and Li,
which is defined using GapP functions. Although it is an important class as the
best upperbound of BQP, its definition seems to be somehow artificial, and
therefore it would ...
Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, Seiichiro Tani
   Sep 2014
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 clean qubit, and only a single output qubit is measured at
the end of ...
Tomoyuki Morimae
   Aug 2014
The process matrix framework [O. Oreshkov, F. Costa, and C. Brukner, Nature
Communications {\bf3}, 1092 (2012)] can describe general physical theory where
locally operations are described by completely-positive maps but globally no
fixed causal st...
Tomoyuki Morimae
   Aug 2014
The process matrix framework [O. Oreshkov, F. Costa, and C. Brukner, Nature
Communications {\bf3}, 1092 (2012)] can describe general physical theory where
locally operations are described by completely-positive maps but globally no
fixed causal st...
Tomoyuki Morimae, Takeshi Koshiba
Quantum Information and Computation 19, 0214-0221 (2019)      Jul 2014
Blind quantum computing protocols enable a client, who can generate or
measure single-qubit states, to delegate quantum computing to a remote quantum
server protecting the client's privacy (i.e., input, output, and program). With
current technolog...
Tomoyuki Morimae, Takeshi Koshiba
   Jul 2014
The first generation quantum computer will be implemented in the cloud style,
since only few groups will be able to access such an expensive and
high-maintenance machine. How the privacy of the client can be protected in
such a cloud quantum compu...
Tomoyuki Morimae, Takeshi Koshiba
   May 2014
Deterministic quantum computation with one quantum bit (DQC1), or the one
clean qubit model, [E. Knill and R. Laflamme, Phys. Rev. Lett. {\bf81}, 5672
(1998)] is a model of quantum computing where the input is the tensor product
of a single pure q...
MORIMAE Tomoyuki
Technical report of IEICE. ISEC   114(24) 29-34   May 2014
Device independence is an important concept in quantum cryptography, which means that it is not necessary to trust devices used in the protocol. In this paper, we study device independence of the verifiable blind quantum computing by using the no-...
Tomoyuki Morimae
Phys. Rev. A 90, 010101(R) (2014)      Apr 2014
In the measurement-based quantum computing, there is a natural "causal cone"
among qubits of the resource state, since the measurement angle on a qubit has
to depend on previous measurement results in order to correct the effect of
byproduct opera...
Tomoyuki Morimae
   Mar 2014
We show that a highly-mixed state in terms of a large min-entropy is useless
as a resource state for measurement-based quantum computation in the sense that
if a classically efficiently verifiable problem is efficiently solved with such
a highly-m...
FUJII Keisuke, MORIMAE Tomoyuki
IEICE technical report. Theoretical foundations of Computing   113(488) 23-27   Mar 2014
Instantaneous quantum polynomial-time (IQ P) computation is a class of quantum computation consisting only of commuting two-qubit gates and is not universal in the sense of standard quantum computation. Nevertheless, it has been shown that if ther...
MORIMAE Tomoyuki, FUJII Keisuke, FITZSIMONS Joseph
IEICE technical report. Theoretical foundations of Computing   113(488) 17-21   Mar 2014
Deterministic quantum computation with one quantum bit (DQC1) is a model of quantum computing where the input restricted to containing a single qubit in a pure state and with all other qubits in a completely-mixed state, with only a single qubit m...
Basics and applications of measurement-based quantum computing
2014 INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY AND ITS APPLICATIONS (ISITA)   327-330   2014   [Refereed]
Tomoyuki Morimae, Keisuke Fujii, Joseph F. Fitzsimons
Phys. Rev. Lett. 112, 130502 (2014)      Dec 2013
Deterministic quantum computation with one quantum bit (DQC1) is a model of
quantum computing where the input restricted to containing a single qubit in a
pure state and with all other qubits in a completely-mixed state, with only a
single qubit m...
Keisuke Fujii, Tomoyuki Morimae
New J. Phys. 19 033003 (2017)      Nov 2013
Instantaneous quantum polynomial-time (IQP) computation is a class of quantum
computation consisting only of commuting two-qubit gates and is not universal
in the sense of standard quantum computation. Nevertheless, it has been shown
that if there...
Keisuke Fujii, Tomoyuki Morimae
   Nov 2013
Instantaneous quantum polynomial-time (IQP) computation is a class of quantum
computation consisting only of commuting two-qubit gates and is not universal
in the sense of standard quantum computation. Nevertheless, it has been shown
that if there...
Tomoyuki Morimae
Nature Physics 9, 693 (2013)      Oct 2013
Alice, who does not have any sophisticated quantum technology, delegates her
quantum computing to Bob, who has a fully-fledged quantum computer. Can she
check whether the computation Bob performs for her is correct? She cannot
recalculate the resu...
Tomoyuki Morimae
Phys. Rev. A 91, 042335 (2015)      Jun 2013
We show that at least 2kTln2 of heat dissipation per qubit occurs in
measurement-based quantum computation according to Landauer's principle. This
result is derived by using only the fundamental fact that quantum physics
respects the no-signaling ...
Vittorio Giovannetti, Lorenzo Maccone, Tomoyuki Morimae, Terry G. Rudolph
Phys. Rev. Lett. 111, 230501 (2013)      Jun 2013
We give a cheat sensitive protocol for blind universal quantum computation
that is efficient in terms of computational and communication resources: it
allows one party to perform an arbitrary computation on a second party's
quantum computer withou...
Tomoyuki Morimae, Takeshi Koshiba
   Jun 2013
Blind quantum computing [A. Broadbent, J. Fitzsimons, and E. Kashefi,
Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer
Science 517 (2009)] is a secure cloud quantum computing protocol which enables
a client (who does not ha...
Tomoyuki Morimae, Keisuke Fujii
Phys. Rev. Lett. 111, 020502 (2013)      Feb 2013
Blind quantum computation is a new secure quantum computing protocol where a
client, who does not have enough quantum technologies at her disposal, can
delegate her quantum computation to a server, who has a fully-fledged quantum
computer, in such...
Takahiro Sueki, Takeshi Koshiba, Tomoyuki Morimae
Phys. Rev. A 87, 060301 (R), 2013      Oct 2012
Blind quantum computation is a new quantum secure protocol, which enables
Alice who does not have enough quantum technology to delegate her computation
to Bob who has a fully-fledged quantum power without revealing her input,
output and algorithm....
Tomoyuki Morimae
Int. J. Quant. Inf. 12, 1450026 (2014)      Aug 2012
Measurement-based quantum computation is a novel model of quantum computing
where universal quantum computation can be done with only local measurements on
each particle of a quantum many-body state, which is called a resource state.
One large dif...
Tomoyuki Morimae
Phys. Rev. A 89, 060302(R) (2014)      Aug 2012
Blind quantum computing is a new secure quantum computing protocol where a
client who does not have any sophisticated quantum technlogy can delegate her
quantum computing to a server without leaking any privacy. It is known that a
client who has o...
Tomoyuki Morimae
Phys. Rev. Lett. 109, 230502 (2012)      Aug 2012
Blind quantum computation is a secure delegated quantum computing protocol
where Alice who does not have sufficient quantum technology at her disposal
delegates her computation to Bob who has a fully-fledged quantum computer in
such a way that Bob...
Pierre Alquier, Cristina Butucea, Mohamed Hebiri, Katia Meziani, Morimae Tomoyuki
   Jun 2012
We introduce a new method to reconstruct the density matrix Tex of a
system of Tex-qubits and estimate its rank Tex from data obtained by quantum
state tomography measurements repeated Tex times. The procedure consists in
minimizing the risk of...
Tomoyuki Morimae, Keisuke Fujii
Phys. Rev. A 87, 050301(R) (2013)      Jan 2012
Blind quantum computation is a new secure quantum computing protocol which
enables Alice who does not have sufficient quantum technology to delegate her
quantum computation to Bob who has a fully-fledged quantum computer in such a
way that Bob can...
Keisuke Fujii, Tomoyuki Morimae
Phys. Rev. A 85, 010304(R) (2012)      Nov 2011
Recently, Li {\it et al.} [Phys. Rev. Lett. {\bf 107}, 060501 (2011)] have
demonstrated that topologically protected measurement-based quantum computation
can be implemented on the thermal state of a nearest-neighbor two-body
Hamiltonian with spin...
Tomoyuki Morimae, Keisuke Fujii
Nature Communications 3, 1036 (2012)      Oct 2011
Blind quantum computation is a novel secure quantum-computing protocol that
enables Alice, who does not have sufficient quantum technology at her disposal,
to delegate her quantum computation to Bob, who has a fully fledged quantum
computer, in su...
Tomoyuki Morimae, Keisuke Fujii
Supplementary material of Sci. Rep. 2, 508 (2012); arXiv:1106.3720      Oct 2011
In the framework of quantum computational tensor network [D. Gross and J.
Eisert, Phys. Rev. Lett. {\bf98}, 220503 (2007)], which is a general framework
of measurement-based quantum computation, the resource many-body state is
represented in a ten...
Tomoyuki Morimae, Keisuke Fujii
Scientific Reports 2, 508 (2012)      Jun 2011
In the framework of quantum computational tensor network, which is a general
framework of measurement-based quantum computation, the resource many-body
state is represented in a tensor-network form, and universal quantum
computation is performed i...
Keisuke Fujii, Tomoyuki Morimae
Phys. Rev. A 85 032338 (2012)      Jun 2011
We investigate relations between computational power and correlation in
resource states for quantum computational tensor network, which is a general
framework for measurement-based quantum computation. We find that if the size
of resource states i...
Tomoyuki Morimae
Phys. Rev. A 85, 062328 (2012)      Dec 2010
The string-net condensate is a new class of materials which exhibits the
quantum topological order. In order to answer the important question, "how
useful is the string-net condensate in quantum information processing?", we
consider the most basic...
Tomoyuki Morimae, Jonas Kahn
Phys. Rev. A 82, 052314 (2010)      Nov 2010
It was shown in [T. Morimae, Phys. Rev. A {\bf81}, 060307(R) (2010)] that the
gate fidelity of an inaccurate one-way quantum computation is upper bounded by
a decreasing function of the amount of entanglement in the register. This means
that a str...
Tomoyuki Morimae, Vedran Dunjko, Elham Kashefi
Quantum Information and Computation 15, pp0200-0234 (2015)      Sep 2010
The blind quantum computing protocols (BQC) enable a classical client with
limited quantum technology to delegate a computation to the quantum server(s)
in such a way that the privacy of the computation is preserved. Here we present
a new scheme f...
Tomoyuki Morimae
Phys. Rev. A 83, 042337 (2011)      Jul 2010
In the framework of the computational tensor network [D. Gross and J. Eisert,
Phys. Rev. Lett. {\bf98}, 220503 (2007)], the quantum computation is performed
in a virtual linear space which is called the correlation space. It was
recently shown [J....
Tomoyuki Morimae
Phys. Rev. A 81, 060307(R) (2010)      Mar 2010
We study how entanglement among the register qubits affects the gate fidelity
in the one-way quantum computation if a measurement is inaccurate. We derive an
inequality which shows that the mean gate fidelity is upper bounded by a
decreasing funct...
Tomoyuki Morimae
Phys. Rev. A 81 060304(R) (2010)      Feb 2010
It is well known that magnons, elementary excitations in a magnetic material,
behave as bosons when their density is low. We study how the bosonic character
of magnons is governed by the amount of a multipartite entanglement in the
vacuum state on...
Tomoyuki Morimae
Phys. Rev. A 81, 022304 (2010).      Jan 2010
We investigate low-temperature coherence properties of the Z_2 quantum memory
which is capable of storing the information of a single logical qubit. We show
that the memory has superposition of macroscopically distinct states for some
values of a ...
Tomoyuki Morimae
Phys. Rev. A 81, 010101 (R) (2010)      Dec 2009
We show relations between superposition of macroscopically distinct states
and entanglement. These relations lead to the important conclusion that if a
state contains superposition of macroscopically distinct states, the state also
contains large ...
Tomoyuki Morimae
Phys. Rev. A 80, 012105 (2009)      Jul 2009
We consider the creation of superpositions of macroscopically distinct states
by a completely-positive (CP) operation on a subsystem. We conclude that the
subsystem on which the CP operation acts must be macroscopically large if the
success probab...
Tomoyuki Morimae, Akira Shimizu
Phys. Rev. A 74, 052111 (2006)      Aug 2006
We propose a method of visualizing superpositions of macroscopically distinct
states in many-body pure states. We introduce a visualization function, which
is a coarse-grained quasi joint probability density for two or more hermitian
additive oper...
Akira Shimizu, Tomoyuki Morimae
Phys. Rev. Lett. 95, 090401 (2005)      Apr 2005
We propose a correlation of local observables on many sites in macroscopic
quantum systems. By measuring the correlation one can detect, if any,
superposition of macroscopically distinct states, which we call macroscopic
entanglement, in arbitrary...
Akira Shimizu, Tomoyuki Morimae
Phys. Rev. Lett. 95, 090401 (2005)      Apr 2005
We propose a correlation of local observables on many sites in macroscopic
quantum systems. By measuring the correlation one can detect, if any,
superposition of macroscopically distinct states, which we call macroscopic
entanglement, in arbitrary...