Date: 7 and 8th of December 2015

Place: Tokyo Institute of Technology (Tamachi Campus), Japan

**Invited
speakers:**

**Adam
Bouland (MIT)**

The
space "just above" BQP

We explore the space
"just above" BQP by defining a complexity class CQP
(Collapse-free Quantum Polynomial time) which is larger than BQP but
does not contain NP relative to an oracle. The class is defined by
imagining that quantum computers can perform measurements that do not
collapse the wavefunction. This (non-physical) model of computation
can efficiently solve problems such as Graph Isomorphism and
Approximate Shortest Vector which are believed to be intractable for
quantum computers. Furthermore, it can search an unstructured
N-element list in O(N^{1/3}) time, but no faster than N^{1/4}, and
hence cannot solve NP-hard problems in a black box manner. In short,
this model of computation is more powerful than standard quantum
computation, but only slightly so. This is surprising as most
modifications of BQP increase the power of quantum computation to NP
or beyond.

Based on joint work with Scott Aaronson, Joe
Fitzsimons, and Mitchell Lee.

**Michael
Bremner (University of Technology Sydney)**

Average-case complexity versus approximate simulation of commuting quantum computations

We use the class of commuting quantum computations known as IQP (Instantaneous Quantum Polynomial time) to strengthen the conjecture that quantum computers are hard to simulate classically. We show that, if either of two plausible average-case hardness conjectures holds, then IQP computations are hard to simulate classically up to constant additive error. One conjecture relates to the hardness of estimating the complex-temperature partition function for random instances of the Ising model; the other concerns approximating the number of zeroes of random low-degree polynomials. We observe that both conjectures can be shown to be valid in the setting of worst-case complexity. We arrive at these conjectures by deriving spin-based generalisations of the Boson Sampling problem that avoid the so-called permanent anticoncentration conjecture.

**Giulio
Chiribella (University of Hong Kong)**

Quantum computations without definite causal structure

In principle, Quantum theory allows for higher order transformations that cannot be realized by inserting the input black boxes within a circuit in a predefined causal order. A simple example is the quantum switch [1,2], wherein two input black boxes are arranged in two different orders depending on the state of a control qubit, leading to an output operation where the causal relation between the two boxes is in a quantum superposition. Considering such higher order transformations is interesting at the fundamental level, as such causally indefinite operations could become physically achievable in quantum gravity scenarios yet to be explored. From the information-theoretic point of view, a computational model that includes black box transformations like the quantum switch would offer advantages in a number of tasks, including the discrimination and classification of quantum channels [3]. In this talk I will review the most general black box transformations allowed by quantum mechanics, showing how circuits with both definite and indefinite causal structures can be reconstructed from the basic structure of the quantum state space.

[1] GC, G. M. D'Ariano, P. Perinotti, B. Valiron, Beyond quantum computers, arXiv:0912.0195.

[2] GC, G. M. D'Ariano, P. Perinotti, B. Valiron, Quantum computations without definite causal structure, Phys. Rev. A 88, 022318 (2013)

[3] GC, Perfect discrimination of no-signalling channels via quantum superposition of causal structures, Phys. Rev. A 86, 040301(R) (2012)

**Keisuke
Fujii (Kyoto University)**

Computational quantum-classical boundary of complex and noisy quantum systems

It is often said that the transition from quantum to classical worlds is caused by decoherence originated from an interaction between a system of interest and its surrounding environment. Here we establish a computational quantum-classical boundary from the viewpoint of classical simulatability of a quantum system under decoherence. Specifically, we consider commuting quantum circuits being subject to decoherence. Or equivalently, we can regard them as measurement-based quantum computation on decohered weighted graph states. To show intractability of classical simulation above the boundary, we utilize the postselection argument introduced by M. J. Bremner, R. Jozsa, and D. J. Shepherd [Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science 465, 1413 (2009).] and crucially strengthen its statement by taking noise effect into account. Classical simulatability below the boundary is also shown constructively by using both separable criteria in a projected-entangled-pair-state picture and the Gottesman-Knill theorem for mixed state Clifford circuits. We found that when each qubit is subject to a single-qubit complete-positive-trace-preserving noise, the computational quantum-classical boundary is sharply given by the noise rate required for the distillability of a magic state. The obtained quantum-classical boundary of noisy quantum dynamics reveals a complexity landscape of controlled quantum systems. This paves a way to an experimentally feasible verification of quantum mechanics in a high complexity limit beyond classically simulatable region.

**Stephen
Jordan (NIST)**

Permutational
quantum computing

In topological quantum computation the
geometric details of a particle trajectory are irrelevant; only the
topology matters. Taking this one step further, we consider a model
of computation that disregards even the topology of the particle
trajectory, and computes by permuting particles. Whereas topological
quantum computation requires anyons, permutational quantum
computation can be performed with ordinary spin-1/2 particles, using
a variant of the spin-network scheme of Marzuoli and Rasetti. We do
not know whether permutational computation is universal. It may
represent a new complexity class within BQP. Nevertheless,
permutational quantum computers can in polynomial time approximate
matrix elements of certain irreducible representations of the
symmetric group and simulate certain processes in the Ponzano-Regge
spin foam model of quantum gravity. No polynomial time classical
algorithms for these problems are known.

**Gen
Kimura (Shibaura Institute of Technology)**

Geometrical appearance of Tsirelson bound in general probabilistic models

We investigate the structure of entangled states in general probabilistic theories, operationally the most general framework of any probabilistic models. In particular, we discuss how Tsirelson bound appears in the asymptotic limit of the numbers of vertexes in the local state spaces.

**Ciaran
Lee (Oxford University)**

The computational landscape of general physical theories

From
the general difficulty of simulating quantum systems using classical
systems, and in particular the existence of an efficient quantum
algorithm for factoring, it is likely that quantum computation is
intrinsically more powerful than classical computation. At present,
the best upper bound known for the power of quantum computation is
that BQP is in AWPP, where AWPP is a classical complexity class
(known to be included in PP, hence PSPACE). In this talk I will
discuss the limits on computational power that are imposed by simple
physical, or information theoretic, principles. To this end, I will
define a circuit-based model of computation in a class of
operationally-defined theories more general than quantum theory, and
ask: what is the minimal set of physical assumptions under which the
above inclusions still hold? I will show that given only the
assumption of tomographic locality (roughly, that multipartite states
and transformations can be characterised by local measurements),
efficient computations are contained in AWPP. This inclusion still
holds even without assuming a basic notion of causality (where the
notion is, roughly, that probabilities for outcomes cannot depend on
future measurement choices). Then, following Aaronson, I extend the
computational model by allowing post-selection on measurement
outcomes. Aaronson showed that the corresponding quantum complexity
class, PostBQP, is equal to PP. Given only the assumption of
tomographic locality, the inclusion in PP still holds for
post-selected computation in general theories. Hence in a world with
post-selection, quantum theory is optimal for computation in the
space of all operational theories. I will then discuss a physically
motivated model of computation -- which takes its inspiration from
the phenomenon of destructive interference witnessed in**
**quantum
theory -- that perfectly captures the class AWPP. This model will be
shown to correspond to an operationally-defined theory satisfying
tomographic locality, thus showing that containment in AWPP is tight
for general theories. I will conclude by discussing future research
directions. Based on arXiv:1412.8671 and subsequent work. Joint with
Jon Barrett, Niel de Beaudrap and Matty Hoban.

**Harumichi
Nishimura****@****(Nagoya
University)**

Power of Quantum Computation with Few Clean Qubits

We
investigate the power of polynomial-time quantum computation in which
only a very limited number of qubits are initially clean, and all the
remaining qubits are initially in the totally mixed state. Neither
initializations of qubits nor intermediate measurements are allowed
during the computation. The main results are unexpectedly strong
error-reducible properties of such quantum computations. It is proved
that any problem solvable by a polynomial-time quantum computation
with one-sided bounded error that uses logarithmically many clean
qubits can also be solvable with exponentially small one-sided error
using just two clean qubits, and with polynomially small one-sided
error using just one clean qubit (which in particular implies the
solvability with any small constant one-sided error). It is further
proved in the case of two-sided bounded error that any problem
solvable by such a computation with a constant gap between
completeness and soundness using logarithmically many clean qubits
can also be solvable with exponentially small two-sided error using
just two clean qubits. If only one clean qubit is available, the
problem is again still solvable with exponentially small error in one
of the completeness and soundness and polynomially small error in the
other. As an immediate consequence of the above result for the
two-sided-error case, it follows that the Trace Estimation problem
defined with fixed constant threshold parameters is complete for the
classes of problems solvable by polynomial-time quantum computations
with completeness 2/3 and soundness 1/3 using logarithmically many
clean qubits and just one clean qubit, respectively. The techniques
used for proving the error-reduction results may be of independent
interest in themselves, and one of the technical tools can also be
used to show the hardness of weak classical simulations of
one-clean-qubit computations (i.e., DQC1 computations). This is a
joint work with Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae,
Shuhei Tamate, and Seiichiro Tani.

**Ognyan
Oreshkov (ULB)**

Quantum theory with indefinite causal structure

Quantum theory can be understood as a theory of information processing in the circuit framework for operational probabilistic theories. This approach presupposes a definite casual structure as well as a preferred time direction. But in general relativity, the causal structure of space-time is dynamical and not predefined. This indicates that a quantum theory that could incorporate gravity requires a more general operational paradigm. In this talk, I will describe recent progress in this direction. First, I will show how relaxing the assumption that local operations take place in a global causal structure leads to a generalized framework that unifies all signaling and non-signaling quantum correlations in space-time via an extension of the density matrix called the process matrix. This framework also contains a new kind of correlations incompatible with any definite causal structure, which violate causal inequalities, the general theory of which I am going to present. I will then present an extension of the process matrix framework, in which no predefined causal structure is assumed even locally. This is based on a more general, time-neutral notion of operation, which leads to new insights into the problem of time-reversal symmetry in quantum mechanics, the meaning of causality, and the fact that we remember the past but not the future. In the resultant generalized formulation of quantum theory, operations are associated with regions that can be connected in networks with no directionality assumed for the connections. The theory is compatible with timelike loops and other acausal structures.

**Jamie
Sikora (CQT, Singapore)**

Ground state connectivity of local Hamiltonians

The study of ground state energies of local Hamiltonians has played a fundamental role in quantum complexity theory. In this paper, we take a new direction by introducing the physically motivated notion of "ground state connectivity" of local Hamiltonians, which captures problems in areas ranging from quantum stabilizer codes to quantum memories. We show that determining how "connected" the ground space of a local Hamiltonian is can range from QCMA-complete to NEXP-complete. As a result, we obtain a natural QCMA-complete problem, a goal which has generally proven difficult since the conception of QCMA over a decade ago. Our proofs rely on a new technical tool, the Traversal Lemma, which analyzes the Hilbert space a local unitary evolution must traverse under certain conditions. We show that this lemma is tight up to a polynomial factor with respect to the length of the unitary evolution in question. This is joint work with Sevag Gharibian, arXiv:1409.3182.

**Program:**

7th

9:40-10:20 Giulio Chiribella

10:20-11:00 Ognyan Oreshkov

11:00-11:20 break

11:20-12:00 Gen Kimura

12:00-13:40 lunch

13:40-14:20 Ciaran Lee

14:20-15:00 Tomoyuki Morimae

15:00-15:20 break

15:20-16:00 Keisuke Fujii

8th

9:40-10:20 Jamie Sikora

10:20-11:00 Harumichi Nishimura

11:00-11:20 break

11:20-12:00 Adam Bouland

12:00-13:40 lunch

13:40-14:20 Stephen Jordan

14:20-15:00 Michael Bremner

15:00-15:20 break

15:20-16:00

**Registration:**

This workshop is free of charge and open to anyone. No registration is needed.

**Venue:**

The workshop will be held in Tokyo Institute of Technology Tamachi Campus

http://www.titech.ac.jp/english/about/campus_maps/tamachi.html

**Organizer:**

Tomoyuki Morimae (Gunma University) Email: [my family name] at gunma-u.ac.jp

Ryuhei Mori (Tokyo Institute of Technology)