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...

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...

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-, ,
and 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...

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...

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...

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...

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...

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. ...

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...

Quantum Information and Computation 17, pp 0959-0972 (2017) Apr 2017

We study how complexity classes above BQP, such as postBQP, , 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...

Hypergraph states are generalizations of graph states where controlled-
gates on edges are replaced with generalized controlled- gates on
hyperedges. Hypergraph states have several advantages over graph states. For
example, certain hypergrap...

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...

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...

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 ...

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...

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...

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 and soundness , 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]

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...

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 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...

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...

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 ...

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 ...

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...

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 ...

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 ...

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...

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...

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...

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...

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...

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-...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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....

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...

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...

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 of a
system of -qubits and estimate its rank from data obtained by quantum
state tomography measurements repeated times. The procedure consists in
minimizing the risk of...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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....

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...

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...

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 ...

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 ...

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...

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...

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...

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...