Workshop around BQP

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.



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


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



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


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


Tomoyuki Morimae (Gunma University) Email: [my family name] at

Ryuhei Mori (Tokyo Institute of Technology)

inserted by FC2 system