AJW2014

Measurement-based quantum computation employs many-body entangled states as resources for quantum computation. This paradigm provides a good framework to discuss a connection between quantum information science and many-body physics. In this talk, we report measurement-based quantum computation on thermal states of the interacting cluster Hamiltonian that undergoes thermal phase transitions. We show that the long-range order of the symmetry breaking thermal states drastically enhances the robustness of MBQC against thermal excitations. Specifically, we show that MBQC is topologically protected below the critical temperature in three-dimensional cases.

Security problem is a central issue in quantum information. To discuss this topic, we usually employ information quantities. In this talk, we explain several kinds of generalized entropies in quantum system. Then, I explain how to use these generalized entropies in quantum security. I also explain how to use the other information quantities in other tasks.

Quantum physics provides unconditionally secure blind computation schemes. We show that the framework of blind quantum computation provides a methodology to discuss the communication complexity of one-sided secure cryptographic protocols. For the methodology, we introduce a notion of partially blind quantum computation and incorporate it into a technique of reducing communication complexity of some tasks with respect to the privacy by using the advantage of quantum algorithms over classical ones. As example, we take quantum private information retrieval and show a quantum PIR protocol that has the communication complexity poly(log N ), where N is the database size. We note that our results do not contradict the lower bounds on the communication complexity of QPIR.

A secret sharing scheme encodes a secret to multiple shares so that only qualified sets of shares can perfectly reconstruct the secret. Secret and shares can be either classical or quantum. Most studies on the secret sharing scheme focus on the perfect scheme, with which a non-qualified share set has zero information about the secret. The main drawback of the perfect scheme is that the share size must be larger than or equal to the secret. The ramp secret sharing schemes overcome this drawback by allowing partial information leakage from non-qualified sets. But the ramp schemes also introduce a new risk. Suppose that the secret is username:password, a share set has 8-symbol information about the secret, which does not enable the perfect reconstruction. The partial information recoverable by the share set may be the "password" part, which is very undesirable. To exclude such a possibility, Yamamoto introduced the notion of strong security for the classical ramp schemes. In this study, we introduce a corresponding quantum definition of the strong security, and propose an explicit construction.

Blind quantum computing [Broadbent, Fitzsimons, and Kashefi, FOCS2009] is a secure protocol of delegated quantum computing where a client who does not have any quantum computer can delegate her quantum computing to a remote server who has a universal quantum computer in such a way that client's privacy is guaranteed. In this talk, I will explain our recent results about blind quantum computing including topological blind quantum computing and device-independent blind quantum computing.

This work 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 classical public coins even in the quantum setting, the present work introduces a generalized version of quantum Arthur-Merlin games where the public coins can be quantum as well: the verifier can send not only random bits, but also halves of EPR pairs. First, it is proved that the class of two-turn quantum Arthur-Merlin games with quantum public coins, denoted qq-QAM, does not change by adding a constant number of turns of classical interactions prior to the communications of the qq-QAM proof systems. This can be viewed as a quantum analogue of the celebrated collapse theorem for AM due to Babai. To prove this collapse theorem, this work provides a natural complete problem for qq-QAM: deciding whether the output of a given quantum circuit is close to a totally mixed state. This complete problem is on the very line of the previous studies investigating the hardness of checking the properties related to quantum circuits, and is of independent interest. It is further proved that the class qq-QAM_1 of two-turn quantum-public-coin quantum Arthur-Merlin proof systems with perfect completeness gives new bounds for standard well-studied classes of two-turn interactive proof systems. Finally, the collapse theorem above is extended to comprehensively classify the role of interaction and public coins in quantum Arthur-Merlin games: it is proved that, for any constant m>1, the class of problems having an m-turn quantum Arthur-Merlin proof system is either equal to PSPACE or equal to the class of problems having a two-turn quantum Arthur-Merlin game of a specific type, which provides a complete set of quantum analogues of Babai's collapse theorem. This is a joint work with Hirotada Kobayashi and Francois Le Gall.

The classical Renyi relative entropies play a central role in classical information theory through large deviation theory such as Cramer's theorem or Sanov's Theorem. The Renyi relative entropies also provide an information geometrical point of view in large deviation theory, as the potential functions (the logarithm of the partition function) of exponential families connecting probability distributions by e-geodesic.

In quantum systems, however, we can consider various non-equivalent analogues of the Renyi relative entropy, due to non-commutativity of operators. In this presentation, we treat the following three different quantities and elucidate their properties, relations, and operational roles. Then we show formulas to determine the strong converse exponent in quantum hypothesis testing and classical-quantum channel coding.

(1) quantum f-divergence (quasi-entropy by Petz) of Wigner-Yanase-Dyson type
(2) Sandwiched Renyi relative entropy recently proposed in [1,2]
(3) Canonical correlation related to Mori-Kubo-Bogoliubov inner product
(Joint work [3,4,5] with Milan Mosonyi)
[1] M. M.-Lennert, F. Dupuis, O. Szehr, S. Fehr, and M. Tomamichel, J. Math. Phys., 54, 122203, 2013.
[2] M. Wilde, A. Winter, D. Yang, Commun. Math. Phys., 331, pp. 593-622, 2014.
[3] M. Mosonyi and T. Ogawa, arXiv:1309.3228, 2013, (to appear Commun. Math. Phys., 2014).
[4] M. Mosonyi and T. Ogawa, arXiv:1407.3567, 2014.
[5] M. Mosonyi and T. Ogawa, arXiv:1409.3562, 2014.

Simulation of quantum mechanical systems is a major potential application of quantum computers. Typically the task that needs to be performed is simulation of the evolution of the quantum state under a Hamiltonian. This simulation is not exact, but an approximation to within some allowable error epsilon. Previous methods had computational complexity scaling polynomially 1/epsilon (for example, as 1/sqrt(epsilon)). This is poor scaling in comparison to algorithms in may other areas, where the complexity scales as the logarithm of 1/epsilon, allowing high accuracy. We provide a new algorithm for simulating Hamiltonian evolution with complexity scaling as log(1/epsilon). The method is based on using a product formula, as with many previous algorithms, but we then compress the product formula, providing greatly improved performance.

The efficient simulation of quantum systems is considered to be one of the most exciting potential applications of quantum computing technologies. There is an expectation that specialized quantum simulators can be engineered as a stepping stone to the development of fully universal, fault-tolerant, quantum computers. If this expectation is to be realized we must identify physical systems and sets of observables that are both simple enough to robustly implement in a near-term quantum device, yet remain a challenge to classically simulate. In this talk I will discuss several simple quantum systems that cannot be easily simulated classically that might lead to a convincing demonstration of the classical intractability of quantum simulators.

Statistical Mechanics has provided us with straightforward recipes to compute various physical quantities like magnetisation and energy density of many body classical systems. But more often than not, the application of these recipes is computationally inefficient, as can be seen from very idealised systems. It may be expected that quantum algorithms could help in this regard. I will describe a quantum algorithm for measuring complex temperature partition functions of Ising models which, through appropriate Wick rotations, can be analytically continued to yield estimates for real temperatures. Notably the circuits used are low depth and an estimation of the entire partition function is available. Generically, the problem is still hard even with quantum algorithms but in certain cases of weak frustration the scaling is favourable. Finally I'll discuss how to use these methods to address the dual problem concerning the BQP-hardness of estimating partition functions for classical ferromagnetic Ising models in 2D.

Standard classical error correcting codes use a parity check matrix. Error correction in the quantum case proceeds similarly, but after the removal of violated parity checks (defects), we allow certain "local'' operations to have occurred. This leads to a topological view of error correction. In this talk we extend to the non-abelian setting: defects can now braid around each other in non-trivial ways. Condensed matter physicists think of these defects as particles, and we examine a system where such particles behave as "Fibonacci anyons''. We use numerics to demonstrate a threshold for error correction below which quantum information can be recovered with asymptotic certainty.

The framework of measurement-based quantum computation (MBQC) allows us to view the ground states of local Hamiltonians as potential resources for universal quantum computation. A central goal in this field is to find models with ground states that are universal for MBQC and that are also natural in the sense that they involve only two-body interactions and have a small local Hilbert space dimension. Graph states are the original resource states for MBQC, and while it is not possible to obtain graph states as exact ground states of two-body Hamiltonians here we construct two-body frustration-free Hamiltonians that have arbitrarily good approximations of graph states as unique ground states. The construction involves taking a two-body frustration-free model that has a ground state convertible to a graph state with stochastic local operations, then deforming the model such that its ground state is close to a graph state. Each graph state qubit resides in a subspace of a higher dimensional particle. This deformation can be applied to two-body frustration-free Affleck-Kennedy-Lieb-Tasaki (AKLT) models, yielding Hamiltonians that are exactly solvable with exact tensor network expressions for ground states. For the star-lattice AKLT model, the ground state of which is not expected to be a universal resource for MBQC, applying such a deformation appears to enhance the computational power of the ground state, promoting it to a universal resource for MBQC. Transitions in computational power, similar to percolation phase transitions, can be observed when Hamiltonians are deformed in this way. Improving the fidelity of the ground state comes at the cost of a shrinking gap. While analytically proving gap properties for these types of models is difficult in general, we provide a detailed analysis of the deformation of a spin-1 AKLT state to a linear graph state.

We study the possibility of communicating classical information unambiguously with noisy quantum channels where the receiver can either correctly recover the classical message sent by the sender or simply claim an uncertain outcome. A notion of unambiguous capacity is introduced to characterize the optimal communication rates one can achieve under unambiguous decoding strategies. We provide a necessary and sufficient condition for the feasibility of unambiguous communication by establishing a connection to the extendibility of Kraus operator space of quantum channels. Consequently, we show that unambiguous capacity can be super-activated: there are two quantum channels both having zero unambiguous capacity can be used jointly to send classical information unambiguously. Finally, we find auxiliary resources such as shared entanglement, classical feedback, or quantum feedback, can considerably improve the unambiguous capacity to achieve the ordinary (small-error) capacity.

Quantum machine learning has received significant attention in recent years and promising progress has been made in the development of quantum algorithms to speed up traditional machine learning tasks. In this work, however, we focus on the study of the information-theoretic upper bounds of sample complexity—how many training samples are sufficient to predict the future behaviour of an unknown target function. This kind of problem is, arguably, one of the most fundamental problems in statistical learning theory and the bounds for practical settings can be completely characterised by a simple measure of complexity.

Our main result in the paper is that, for learning an unknown quantum measurement, the upper bound, given by the fat-shattering dimension, is linearly proportional to the dimension of the underlying Hilbert space. Learning an unknown quantum state [1] becomes a dual problem to ours, and as a byproduct, we can recover Aaronson’s famous result solely using a classical machine learning technique. In addition, we are able to connect measures of sample complexity with various areas such as quantum state/measurement tomography, quantum state discrimination and quantum random access codes, which may be of independent interest. Lastly, with the assistance of general Bloch- sphere representation, we show that learning quantum measurements/states can be mathematically formulated as a neural network. Consequently, classical ML algorithms can be applied to efficiently accomplish the learning tasks.

[1] S. Aaronson, "The learnability of quantum states," Proc. R. Soc. A, vol. 463, no. 2088, pp. 3089-3144, 2007.

The strong converse property in classical information theory is the fact that any attempt at transmitting information at a rate above capacity will be successful only with a probability that vanishes (exponentially fast) as the number of channel uses increases. In quantum communication we only know a weak converse, which states that the above probability does not converge to one as the number of channel uses goes to infinity. Consequently, it has been an open question to establish a strong converse for the quantum capacity of any non-trivial quantum channel ever since the original works on quantum capacity explicitly stated this as an open question. Our main result is to establish the ''Rains information'' of a quantum channel as a strong converse bound for quantum communication. We then show how this settles the strong converse question for the quantum capacity of all generalized dephasing channels. (This is joint work with Mark M. Wilde and Andreas Winter.)

This paper introduces a new notion of quantum recursion of which the control flow of the computation is quantum rather than classical as in the notions of recursion considered in the previous studies of quantum programming. A typical example is recursive quantum walks, which are obtained by slightly modifying the construction of the ordinary quantum walks. The operational and denotational semantics of quantum recursions are defined by employing the second quantisation method, and they are proved to be equivalent.

Blind Quantum Computing (BQC) allows a client to have a server carry out a quantum computation for them such that the client's inputs, outputs and computation remain private. In this talk I will present a family of protocols for universal unconditionally secure BQC, based on the measurement-based quantum computing model. In the simplest of these protocols the client only needs to be able to prepare single qubits in separable states randomly chosen from a finite set and send them to the server, who has the balance of the required quantum computational resources. I will describe how verification mechanisms can be built on top of such protocols to ensure that any deviation from the prescribed computation by a malicious server is detected with high probability.