Banff Lake Louise Tourism / Paul Zizka Photography
You can attach your poster on any of the available poster boards.
Cosmo Lupo, Mark Wilde and Seth Lloyd. Quantum data hiding in the presence of noise
Kaushik Seshadreesan, Saikat Guha, Masahiro Takeoka and Mark Wilde. Squashed entanglement bounds on entanglement distillation and secret key agreement capacities of quantum channels
Lili Saghafi. NMR, Nuclear Magnetic Resonance Quantum Computing
Valentin Zauner, Damian Draxler, Laurens Vanderstraeten, Jutho Haegeman and Frank Verstraete. Symmetry Breaking and the Geometry of Reduced Density Matrices
We explore to what extent path-integral quantum Monte Carlo methods can efficiently simulate the tunneling behavior of quantum adiabatic optimization algorithms. Specifically we look at symmetric cost functions defined over n bits with a single potential barrier that a successful optimization algorithm will have to tunnel through. The height and width of this barrier depend on n, and by tuning these dependencies, we can make the optimization algorithm succeed or fail in polynomial time. In this article we compare the strength of quantum adiabatic tunneling with that of path-integral quantum Monte Carlo methods. We find numerical evidence that quantum Monte Carlo algorithms will succeed in the same regimes where quantum adiabatic optimization succeeds.
Debasis Mondal, Chandan Datta and Sk Sazim. Quantum Coherence Sets The Quantum Speed Limit For Mixed States
Xueyuan Hu. Extracting coherence by quantum steering
We establish an operational connection between coherence and quantum correlation. When a bipartite state is shared between Alice and Bob, Alice's local selective measurement can induce coherence on Bob's site as long as they are initially quantum correlated, and the maximum coherence she can extract on average can not surpass the initially shared quantum correlation measured by B-side measurement-induced disturbance. Steering-induced coherence (SIC) is introduced to characterize Alice's ability to extract Bob's coherence. For maximally correlated states, the steering-induced coherence is proved to reach the B-side measurement-induced disturbance. When generalized to tripartite scenario, where Bob and Charlie initially share a product state and restricted to use incoherent operations, Alice's local selective measurement can induce the entanglement between Bob and Charlie, and the induced entanglement on average is also bounded from above by the quantum correlation between Alice and Bob. Our results are helful in the study of quantum information protocols such as secret sharing where coherence is a precious resource. Further, since the coherence of a single party is normally robust than bipartite correlations, our results provide a way to ``store'' the quantum correlation as coherence.
Zhu Cao. Discrete-phase-randomized coherent state source and its application in quantum key distribution
Stephanie Wehner, Mark Wilde and Mischa Woods. Work and reversibility in quantum thermodynamics
Hillary Dawkins and Mark Howard. Qutrit Magic State Distillation Tight in Some Directions
Magic state distillation is a crucial component in the leading approaches to implementing universal fault-tolerant quantum computation, with existing protocols for both qubit and higher dimensional systems. Early work focused on determining the region of distillable states for qubit protocols, yet comparatively little is known about which states can be distilled and with what distillable region for d>2. Here we focus on d=3 and present new four-qutrit distillation schemes that improve upon the known distillable region, and achieve distillation tight to the boundary of undistillable states for some classes of state. As a consequence of recent results, this implies that there is a family of quantum states that enable universality if and only if they exhibit contextuality with respect to stabilizer measurements. We also identify a new routine whose fixed point is a magic state with maximal sum-negativity i.e., it is maximally non-stabilizer in a specific sense.
Dawei Ding and Mark Wilde. Strong converse exponents for the feedback-assisted classical capacity of entanglement-breaking channels
In this poster and [1], we propose two types of blind (i.e. unsupervised) processing methods for quantum states or processes. We first introduce a new class of blind quantum source separation (BQSS) methods, for restoring unknown quantum source states only from their coupled version provided by an unknown coupling process. This method performs quantum/classical data conversion by means of spin component measurements, followed by classical processing. It differs from our previous class of classical-processing BQSS methods by using extended types of measurements (three directions, possibly different for the two spins), which yield a more complete BQSS mixing model. This allows us (i) to develop a new disentanglement-based separation procedure, which requires a much lower number of source values for adaptation and (ii) to restore a larger set of sources. This also allowed us to introduce a new research field in [1], namely Blind Quantum Process Tomography (BQPT). BQPT is the blind extension of QPT, i.e. it identifies an unknown quantum process without knowing its input values.
[1] Y. Deville, A. Deville, "From blind quantum source separation to blind quantum process tomography", Proceedings of the 12th International Conference on Latent Variable Analysis and Signal Separation (LVA/ICA 2015), Springer International Publishing Switzerland, LNCS 9237, pp. 184-192, Liberec, Czech Republic, Aug. 25-28, 2015.
We give a strengthening as well as a generalization of an inequality for the quantum conditional mutual information of a tripartite quantum state recently proved by Fawzi and Renner, connecting it with the ability to reconstruct the state from its bipartite reductions. We provide three alternative and simplified proofs ranging from quantum state redistribution via duality of semidefinite programming to elementary properties of pinching maps and the operator logarithm.
Cécilia Lancien. k-extendibility of high-dimensional bipartite quantum states
The idea of detecting the entanglement of a given bipartite state by searching for symmetric extensions of this state was first proposed by Doherty, Parrilo and Spedialeri. The complete family of separability tests it generates, often referred to as the hierarchy of k-extendibility tests, has already proved to be most promising. The goal of this paper is to try and quantify the efficiency of this separability criterion in typical scenarios. For that, we essentially take two approaches. First, we compute the average width of the set of k-extendible states, in order to see how it scales with the one of separable states. And second, we characterize when random-induced states are, depending on the ancilla dimension, with high probability violating or not the k-extendibility test, and compare the obtained result with the corresponding one for entanglement vs separability. The main results can be precisely phrased as follows: on C^d \otimes C^d, when d grows, the average width of the set of k-extendible states is equivalent to (2/\sqrt{k})/d, while random states obtained as partial traces over an environment C^s of uniformly distributed pure states are violating the k-extendibility test with probability going to 1 if s<((k-1)^2/4k)d^2. Both statements converge to the conclusion that, if k is fixed, k-extendibility is asymptotically a weak approximation of separability, even though any of the other well-studied separability relaxations is outperformed by k-extendibility as soon as k is above a certain (dimension independent) value.
We generalize an efficient exact synthesis algorithm for single-qubit unitaries over the Clifford+T gate set which was presented by Kliuchnikov, Maslov and Mosca. Their algorithm takes as input an exactly synthesizable single-qubit unitary--one which can be expressed without error as a product of Clifford and T gates--and outputs a sequence of gates which implements it. The algorithm is optimal in the sense that the length of the sequence, measured by the number of T gates, is smallest possible. In this paper, for each positive even integer n we consider the ``Clifford-cyclotomic'' gate set consisting of the Clifford group plus a z-rotation by pi/n. We present an efficient exact synthesis algorithm which outputs a decomposition using the minimum number of pi/n z-rotations. For the Clifford+T case n=4 the group of exactly synthesizable unitaries was shown to be equal to the group of unitaries with entries over the ring Z[e^{i*pi/n},1/2]. We prove that this characterization holds for a handful of other small values of n but the fraction of positive even integers for which it fails to hold is 100\%.
Bill Fefferman and Shelby Kimmel. Quantum vs Classical Proofs and Subset State Verification
Jamie Sikora, Antonios Varvitsiotis and Zhaohui Wei. Quantum Correlations: Dimension Bounds and Conic Formulations
Cécilia Lancien and Andreas Winter. Parallel repetition and concentration for (sub-)no-signalling games via a flexible constrained de Finetti reduction
Marek Wajs, Su-Yong Lee, Pawel Kurzynski and Dagomir Kaszlikowski. Staterecycling method for testing quantum contextuality
Yimin Ge and Jens Eisert. Area laws and efficient descriptions of quantum many-body states
The random unitary group channels are in general non-degradable. We give upper and lower bounds on their quantum capacity, which differ only up to a factor 2. Our method relies heavily on operator space tools, in particular complex interpolation.
The quantum marginal problem asks whether a set of given density matrices are consistent, i.e., whether they can be the reduced density matrices of a global quantum state. Not many non-trivial analytic necessary (or sufficient) conditions are known for the problem in general. We propose a method to detect consistency of overlapping quantum marginals by considering the separability of some derived states. Our method works well for the $k$-symmetric extension problem in general, and for the general overlapping marginal problems in some cases. Our work is, in some sense, the converse to the well-known $k$-symmetric extension criterion for separability.
Patrick Coles, Eric Metodiev and Norbert Lutkenhaus. Unstructured quantum key distribution
Marco Piani. Hierarchy of efficiently computable quantifiers of the general quantumness of correlations
Francisco Delgado. Bell gems naturally split dynamics information from $SU(2^{2d})$ to $U(1)^{2^{2d-1}-1} \times SU(2)^{2^{2d-1}}$
Quantum Computation and Quantum Information are continuously growing research areas which are based on nature and resources of quantum mechanics, as superposition and entanglement. In its gate array version, the use of convenient and appropriate gates is essential. But while those proposed gates adopt convenient forms for computational algorithms, in the practice, their design depends on specific quantum systems and stuff being used. Gates design is restricted to properties and limitations of interactions and physical elements being involved, where Quantum Control plays a deep role. Quantum complexity of multipartite systems and their interactions requires a tight control to manipulate their quantum states, either local or non-local ones, but still a reducibility procedure should be addressed. This work shows how a general 2d-partite two level spin system in SU(2d) could be decomposed in 2^(2d-1) subsystems on SU(2), letting establish control operations. In particular, it is shown that Bell gems basis is a set of natural states on which decomposition happen naturally under some interaction restrictions. Thus, alternating the direction of local interaction terms in the Hamiltonian, this procedure states a universal exchange semantics on those basis. The structure developed could be understood as a splitting of the 2d information channels into 2 pairs of 2 level information subsystems.
Ching-Yi Lai, Yicong Zheng and Todd Brun. Quantum Calderbank-Shor-Steane Stabilizer State Preparation by Classical Error-Correcting Codes
Eric Chitambar and Min-Hsiu Hsieh. Relating the Resource Theories of Entanglement and Quantum Coherence
Laura Mancinska. Maximally entangled states in pseudo-telepathy games
A pseudo-telepathy game is a nonlocal game which can be won with probability one using some finite-dimensional quantum strategy but not using a classical one. Our central question is whether there exist two-party pseudo-telepathy games which cannot be won with probability one using any maximally entangled state. Towards answering this question, we develop conditions under which maximally entangled states suffice. In particular, we show that maximally entangled states suffice for weak projection games which we introduce as a relaxation of projection games. Our results also imply that any pseudo-telepathy weak projection game yields a device-independent certification of a maximally entangled state. In particular, by establishing connections to the setting of communication complexity, we exhibit a class of games $G_n$ for testing maximally entangled states of local dimension $\Omega(n)$. We leave the robustness of these self-tests as an open question.
We show an equivalence between 1-query quantum algorithms and representations by degree-2 polynomials. Namely, a partial Boolean function $f$ is computable by a 1-query quantum algorithm with error bounded by $\epsilon\lt1/2$ iff $f$ can be approximated by a degree-2 polynomial with error bounded by $\epsilon'\lt1/2$. This result holds for two different notions of approximation by a polynomial: the standard definition of Nisan and Szegedy \cite{NS} and the approximation by block-multilinear polynomials recently introduced by Aaronson and Ambainis \cite{AA}.
We also show two results for polynomials of higher degree. First, there is a total Boolean function which requires $\tilde{\Omega}(n)$ quantum queries but can be represented by a block-multilinear polynomial of degree $\tilde{O}(\sqrt{n})$. Thus, in the general case (for an arbitrary number of queries), block-multilinear polynomials are not equivalent to quantum algorithms.
Second, for any constant degree $k$, the two notions of approximation by a polynomial (the standard and the block-multilinear) are equivalent. As a consequence, we solve an open problem from \cite{AA}, showing that one can estimate the value of any bounded degree-$k$ polynomial $p:\{0, 1\}^n \rightarrow [-1, 1]$ with $O(n^{1-\frac{1}{2k}})$ queries.
We introduce a new class of 3D color codes, which we call stacked codes, together with a fault-tolerant transformation that will map logical qubits encoded in 2D color codes into stacked codes and back. The stacked code allows for the transversal implementation of a non-Clifford logical gate, which when combined with the logical Clifford gates that are transversal in the 2D color code give a gate set that is both fault-tolerant and universal without requiring non-stabilizer magic states. We show that the layers forming the stacked code can be unfolded and arranged in a 2D layout. As only Clifford gates can be implemented transversally for 2D topological stabilizer codes, a non-local operation must be incorporated in order to allow for this transversal application of a non-Clifford gate. Our code achieves this operation through the transformation from a 2D color code to the unfolded stacked code induced by measuring only geometrically local stabilizers and gauge operators within the bulk of 2D color codes together with a non-local operator that has support on a 1D boundary between such 2D codes. We believe that this proposed method to implement the non-local operation is a realistic one for 2D stabilizer layouts and would be beneficial in avoiding the large overheads caused by magic state distillation.
One of the most intriguing problem in computer science is the Graph Isomorphism Problem: determining whether two finite graphs are isomorphic. The Subgraph Isomorphism Problem is a generalization of the Graph Isomorphism Problem where one asks whether a graph H is isomorphic to a subgraph of another graph G. Formally, let $H$ be a (non-empty) graph on $n$ vertices, possibly containing isolated vertices.. Let $f_H(G) = 1$ iff the input graph $G$ on $n$ vertices contains $H$ as a (not necessarily induced) subgraph. Let $\alpha_H$ denote the cardinality of a maximum independent set of $H$. In this work we show: \[Q(f_H) = \Omega\left( \sqrt{\alpha_H \cdot n}\right),\] where $Q(f_H)$ denotes the quantum query complexity of $f_H$. As a consequence we obtain a lower bounds for $Q(f_H)$ in terms of several other parameters of $H$ such as the average degree, minimum vertex cover, chromatic number, and the critical probability. We also use the above bound to show that $Q(f_H) = \Omega(n^{3/4})$ for any $H$, improving on the previously best known bound of $\Omega(n^{2/3})$. Until very recently, it was believed that the quantum query complexity is at least square root of the randomized one. Our $\Omega(n^{3/4})$ bound for $Q(f_H)$ matches the square root of the current best known bound for the randomized query complexity of $f_H$, which is $\Omega(n^{3/2})$ due to Gr\"oger. Interestingly, the randomized bound of $\Omega(\alpha_H \cdot n)$ for $f_H$ still remains open. We also study the Subgraph Homomorphism Problem, denoted by $f_{[H]}$, and show that $Q(f_{[H]}) = \Omega(n)$. Finally we extend our results to the $3$-uniform hypergraphs. In particular, we show an $\Omega(n^{4/5})$ bound for quantum query complexity of the Subgraph Isomorphism, improving on the previously known $\Omega(n^{3/4})$ bound. For the Subgraph Homomorphism, we obtain an $\Omega(n^{3/2})$ bound for the same.
We present a method for estimating the probabilities of outcomes of a quantum circuit using Monte Carlo sampling techniques applied to a quasiprobability representation. Our estimate converges to the true quantum probability at a rate determined by the total negativity in the circuit, using a measure of negativity based on the 1-norm of the quasiprobability. If the negativity grows at most polynomially in the size of the circuit, our estimator converges efficiently. These results highlight the role of negativity as a measure of non-classical resources in quantum computation.
R. Gallego, J. Eisert and H. Wilming. Defining work from a resource-theoretic perspective
Kai Chen, Nai-Le Liu, Yu-Lin Zheng, Yi-Zheng Zhen, Zeng-Bing Chen and Jian. Witnessing EPR nonlocality via arbitrary local measurements
Nilanjana Datta, Min-Hsiu Hsieh and Jonathan Oppenheim. An upper bound on the second order asymptotic expansion for the quantum communication cost of state redistribution
If the second law of thermodynamics forbids a transition from one state to another, then it is still possible to make the transition happen by using a sufficient amount of work. But if we do not have access to this amount of work, can the transition happen probabilistically? In the thermodynamic limit, this probability tends to zero, but here we find that for finite-sized systems, it can be finite. We compute the maximum probability of a transition or a thermodynamical fluctuation from any initial state to any final state, and show that this maximum can be achieved for any final state which is block-diagonal in the energy eigenbasis. As a bi-product, we introduce a finite set of thermodynamical monotones related to the thermo-majorization criteria which governs state transitions, and compute the work of transition in terms of them. We also find upper and lower bounds on this transition probability, in terms of the work of transition. These results, which allow one to not take the thermodynamic limit, are made possible by using and extending techniques from quantum information theory, developed in the context of understanding entanglement theory. As a consequence, our results find application in entanglement theory, and we find the amount of entanglement required (or gained) when transforming one pure entangled state into any other.
Johannes Bausch, Toby Cubitt, Angelo Lucia, David Perez-Garcia and Michael Wolf. Extreme Finite Size Effects
Jonathan Barrett, Ciaran Lee, Niel de Beaudrap and Matty Hoban. The computational landscape of generalised probabilistic theories
Understanding the relation between randomness and non-locality is a fundamental question in quantum physics. The non-local correlations observed when measuring entangled quantum particles certify the presence of randomness in the measurement outputs in a way that is independent on the underlying physical realization of these correlations.
Here, we consider the standard scenario in which an entangled state is subjected to local (destructive) general measurements. We provide an upper bound to the amount of certifiable local randomness, and provide strategies attaining the local bound in the case of qubits. This is possible only using general measurements, proving that POVM's provide an advantage over projective measurements for randomness generation. In addition to this, we consider a new scenario in which sequences of (non-destructive) measurements are applied to the entangled state. We show that the amount of randomness in this case is unbounded. This submission merges two independent works on randomness certification from entangled states: arXiv:1505.03837 and arXiv:1510.03394.
Gelo Noel Tabia. Recursive quantum algorithms for integrated optics
We present recursive schemes for implementing quantum Fourier transforms and inversion about the mean in Grover's algorithm using integrated linear optics with path encoded states. Formally, translating a unitary operation into a linear optical network involves a matrix factorization of the unitary matrix into block-diagonal matrices with a maximum block size of 2. By recursive, we mean that a unitary transformation on 2d modes is realized by using a pair of copies of the same operation on d modes. To demonstrate that our recursive circuits are viable in practice, we ran simulations of proof-of-principle experiments using a fabrication model that accounts for realistic sources of errors in silicon-based photonic integrated devices. We found high-fidelity performance for our optical multiport circuits for 2-qubit and 3-qubit quantum Fourier transforms, and for quantum search on 4-item and 8-item databases.
Thomas Wong. Quantum Walks through Potential Barriers
Estimation of the minimum eigenvalue of a quantum Hamiltonian can be formalised as the Local Hamiltonian problem. We study the natural special case of the Local Hamiltonian problem where the same 2-local interaction, with differing weights, is applied across each pair of qubits. First we consider antiferromagnetic/ferromagnetic interactions, where the weights of the terms in the Hamiltonian are restricted to all be of the same sign. We show that for symmetric 2-local interactions with no 1-local part, the problem is either QMA-complete or in StoqMA. In particular the antiferromagnetic Heisenberg and antiferromagnetic XY interactions are shown to be QMA-complete. We also prove StoqMA-completeness of the antiferromagnetic transverse field Ising model. Second, we study the Local Hamiltonian problem under the restriction that the interaction terms can only be chosen to lie on a particular graph. We prove that nearly all of the QMA-complete 2-local interactions remain QMA-complete when restricted to a 2D square lattice. Finally we consider both restrictions at the same time and discover that, with the exception of the antiferromagnetic Heisenberg interaction, all of the interactions which are QMA-complete with positive coefficients remain QMA-complete when restricted to a 2D triangular lattice.
Niel De Beaudrap. Exact gap complexity as quasi-quantum computation
Ravishankar Ramanathan, Jan Tuziemski, Michal Horodecki and Pawel Horodecki. No quantum realization of extremal no-signaling boxes
We show new bounds on the quantum communication cost of single-shot entanglementassisted one-way quantum communication protocols for the quantum state redistribution task and for the sub-tasks quantum state splitting and quantum state merging. Our bounds are tighter than previously known best bounds for the latter two sub-tasks. A key technical tool that we use is a convex-split lemma which may be of independent interest. This differs from other achievability bounds for quantum state redistribution and quantum state merging , which use decoupling by application of random unitary. Convex-split lemma is based on the fact that in a one-way quantum communication protocol, measurement by Alice leads to an ensemble of states on registers owned by Bob and Referee, convex combination of which is the original mixed state shared between Bob and Referee. Through convex-split lemma, we design one such ensemble of states and use it to construct a protocol for the task of quantum state redistribution.
We study unitary 2-designs and decoupling with random diagonal-unitaries. We first show that the alternate application of random diagonal-unitaries in the Pauli-Z and -X bases constitutes a unitary 2-design after a number of repetitions, implying that the process achieves decoupling. We then go on to show that even fewer repetitions are sufficient for achieving decoupling at the same rate as that with Haar random unitaries. These results imply that precise unitary 2-designs are not necessary for achieving the Haar decoupling rate, indicating the possibility to achieve the rate by random unitaries less uniform than 2-designs. We also provide a simple quantum circuit that implements a unitary 2-design and achieves decoupling, which is partitioned into a constant number of commuting parts.
Vlad Gheorghiu, Marcos de Oliveira and Barry Sanders. Nonzero classical discord
André Chailloux, Kaushik Chakraborty and Anthony Leverrier. Relativistic string commitment secure against quantum adversaries
Ryo Wakabari, Sayaka Katakura and Masaki Nakanishi. A Genetic Algorithm for Scheduling Quantum Gates toward Fast Simulation of Quantum Circuits
Philipp Kammerlander and Renato Renner. A mathematical framework for classical thermodynamics
Pantita Palittapongarnpim, Ehsan Zahedinejad and Barry Sanders. Classical Heuristic-Based Machine Learning for Quantum Control Problems
Viv Kendon and Timothy Proctor. Minimal ancilla-mediated quantum gates
Yuval Sanders, Joel Wallman and Barry Sanders. Bounding quantum gate error rate based on reported average fidelity
Eric Chitambar, Ben Fortescue and Min-Hsiu Hsieh. From secrecy-reversible distributions to entanglement-reversible quantum states
Juan Bermejo-Vega and Kevin C. Zatloukal. Abelian Hypergroups and Quantum Computation
Anne Broadbent. How to Verify a Quantum Computation
Shantanav Chakraborty, Leonardo Novo, Andris Ambainis and Yasser Omar. Spatial search by quantum walk is optimal for almost all graphs
In a recent work [Phys. Rev. Lett. 114, 170502 (2015)], Tavakoli et al. derived interesting results by studying classical and quantum random access codes (RACs) in which the parties communicate higher-dimensional systems. They construct quantum RACs with a greater advantage over classical RACs compared to previously considered RACs with binary alphabets. However, these results crucially hinge upon an unproven assertion that the classical strategy "majority-encoding-identity-decoding" leads to the maximum average success probability achievable for classical RACs; in this work we provide a proof of this intuition. We characterize all optimal classical RACs and show that indeed ``majority-encoding-identity-decoding" is one among the several optimal strategies. Along with strengthening the results in Tavakoli et al., our result provides a firm basis for future research on this topic.
A promising technological advancement meant to enlarge our computational means is the quantum computer. Such a device would harvest the natural complexity of the physical world on the quantum scale in order to unfold concrete mathematical problems more efficiently. This is for instance demonstrated by the exponential advantage of Shor's factoring algorithm over the best know previous factoring method. However, while this natural complexity forms the backbone of quantum computing, it also rises important issues. Indeed, the inevitable errors emerging from the implementation of quantum operations are likewise quantum, and hence share a similar level of intricacy.
This annoying feature quickly comes into play when attempting to characterize noisy operations. Process tomography, maybe the most straightforward benchmarking approach, essentially consists in measuring every aspect of operational noise by comparing various input states with their respective outputs. Such procedure suffers from two major drawbacks. First, it is not scalable: the information needed to describe a noise channel grows exponentially in the size of the system. Secondly, data retrieved from process tomography is affected by state preparation and measurement errors (SPAM), which should ideally be distinguished from operational noise.
Standard randomized benchmarking protocol has been introduced to solve both these issues. It deals with the scalability concern by focusing on a single quantity, a figure of merit called the average fidelity. Furthermore, the scheme employs composition of noise channels to infer SPAM-free information. Although it tackles two important obstacles, randomized benchmarking is not exempted from flaws. A significant limitation is that it exclusively characterizes 2-design gate sets. This signifies that only a restricted collection of operations can be portrayed via randomized benchmarking. In particular, small phase shifts like the so-called pi/8-gate, which cannot possibly be part of any 2-design structure, are excluded. This disadvantage especially undermines the protocol since leading proposals for fault-tolerant quantum computing lay on the implemetation of small phase shifts via magic state distillation and gate injection in order to achieve universal quantum computing. Besides being crutial for universality, these gates are likely to be subject to different error rates, since they are conceived via distinct mechanisms.
In our present work, we propose an extension to randomized benchmarking which enables the characterization of gate sets containing any singular qubit operation with finite order. In particular, we propose a protocol which provides an estimate of the average fidelity of the pi/8-gate. This, together with an estimate of the average fidelity of the Clifford generators (which can be done via interleaved randomized benchmarking) provides a SPAM-independent characterization of a universal gate set.
Mischa Woods, Nelly Ng and Stephanie Wehner. The maximum efficiency of nano heat engines depends on more than temperature
Farid Ablayev and Marat Ablayev. The Concept of Cryptographic Quantum Hashing and Quantum Hashing Constructions
Nai-Hui Chia and Sean Hallgren. How hard is deciding trivial versus nontrivial in the dihedral coset problem?
Tsuyoshi Ito, Stacey Jeffery and Shelby Kimmel. Approximate Span Programs, Effective Resistance, and NAND Trees
We develop a method for quantum process tomography that combines the efficiency of compressed sensing with the robustness of randomized benchmarking. Our method is robust to state preparation and measurement errors, and it achieves a quadratic speedup over conventional tomography when the unknown process is a generic unitary evolution.
Our method is based on PhaseLift, a convex programming technique for phase retrieval. We show that this method achieves approximate recovery of almost all signals, using measurements sampled from spherical or unitary 2-designs. This is the first positive result on PhaseLift using 2-designs. We also show that exact recovery of all signals is possible using unitary 4-designs. Previous positive results for PhaseLift required spherical 4-designs, while PhaseLift was known to fail in certain cases when using spherical 2-designs.
We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithm's success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability.
Adrian Hutter, James Wootton and Daniel Loss. Parafermions in a Kagome lattice of qubits for topological quantum computation
Jean-François Biasse and Fang Song. On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in Q(zeta_{p^n})
Nathaniel Johnston, Rajat Mittal, Vincent Russo and John Watrous. Extended nonlocal games and monogamy-of-entanglement games
Adrian Hutter and James Wootton. Threshold Theorems for Topological Quantum Computing
In low-rank matrix recovery, one aims to reconstruct a low-rank matrix from a minimal number of linear measurements. Within the paradigm of compressed sensing, this is made computationally efficient by minimizing the nuclear norm as a convex surrogate for rank. In this work, we identify an improved regularizer based on the so-called diamond norm, a concept imported from quantum information theory. We show that -for a class of matrices saturating a certain norm inequality- the descent cone of the diamond norm is contained in that of the nuclear norm. This suggests superior reconstruction properties for these matrices. We explicitly characterize this set of matrices, which also contains quantum channels. Moreover, we demonstrate numerically that the diamond norm indeed outperforms the nuclear norm in a number of relevant applications: These include not only the task of quantum process tomography but also signal analysis tasks such as blind matrix deconvolution or the retrieval of certain unitary basis changes. The diamond norm is defined for matrices that can be interpreted as order-4 tensors and it turns out that the above condition depends crucially on that tensorial structure. In this sense, this work touches on an aspect of the notoriously difficult tensor completion problem.
Ning Bao, Adam Bouland and Stephen Jordan. Grover search and the no-signaling principle
Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh and Scott Aaronson. Doubly infinite separation of quantum information and communication
Gorjan Alagic and Bill Fefferman. Quantum obfuscation
We extend the connection between degenerate entanglement spectra present in symmetry-protected topological orders (SPTO's) of 1D spin chains and their use in measurement-based quantum computation (MQC) to the setting of 2D systems. We find surprisingly that the 2D cluster state, an archetypal resource state for MQC, is in a trivial 2D SPTO phase, and show, by a more fine-grained classification, that it does have nontrivial SPTO, but of the same nature as 1D spin chains. In contrast, we introduce a new ground state which possesses nontrivial SPTO entirely of a 2D nature, and show that it is universal for MQC. By utilizing genuine higher-dimensional SPTO, our results open up a research avenue to directly harness its greater quantum-gate complexity within the so-called Clifford hierarchy for the first time in MQC.
Hao-Chung Cheng, Min-Hsiu Hsieh and Marco Tomamichel. Uncertainty and Dynamical Evolution of Markov Semigroups on Quantum Ensembles
In the study of Markovian processes, one of the principal achievements is the equivalence between the Phi-Sobolev inequalities and an exponential decrease of the Phi-entropies. In this work, we develop a framework of Markov semigroups on matrix-valued functions and generalize the above equivalence to the exponential decay of matrix Phi-entropies. This result also specializes to spectral gap inequalities and modified logarithmic Sobolev inequalities in the random matrix setting. To establish the main result, we define a non-commutative generalization of the carre du champ operator, and prove a de Bruijn's identity for matrix-valued functions. The proposed Markov semigroups acting on matrix-valued functions have immediate applications in the characterization of the dynamical evolution of quantum ensembles. We consider two special cases of quantum unital channels, namely, the depolarizing channel and the phase-damping channel. In the former, since there exists a unique equilibrium state, we show that the matrix Phi-entropy of the resulting quantum ensemble decays exponentially as time goes on. Consequently, we obtain a stronger notion of monotonicity of the Holevo quantity - the Holevo quantity of the quantum ensemble decays exponentially in time and the convergence rate is determined by the modified log-Sobolev inequalities. However, in the latter, the matrix Phi-entropy of the quantum ensemble that undergoes the phase-damping Markovian evolution generally will not decay exponentially. This is because there are multiple equilibrium states for such a channel. Finally, we also consider examples of statistical mixing of Markov semigroups on matrix-valued functions. We can explicitly calculate the convergence rate of a Markovian jump process defined on Boolean hypercubes, and provide upper bounds of the mixing time on these types of examples.
Adrian Chapman and Akimasa Miyake. How can an autonomous quantum Maxwell demon harness correlated information?
Joonwoo Bae and Dariusz Chruscinski. Operational Characterization to Divisibility of Dynamical Maps: Strict Hierarchy
A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the plain model in both the classical and quantum settings. Here, we show how to use quantum information, together with the assumption of reusable (stateless) hardware tokens, to build statistically secure OTMs. This is in sharp contrast with the classical case, where reusable hardware tokens alone cannot yield OTMs. Our scheme is technologically simple and can be made noise-tolerant. We prove security in the quantum universal composability (UC) framework, employing semi definite programming results of Molina, Vidick and Watrous [TQC 2013] and combinatorial techniques of Pastawski et al. [Proc. Natl. Acad. Sci. 2012].
A special feature of the ground state of a topologically ordered phase is large-scale correlations depending on the topology of the regions. These correlations can be detected by the topological entanglement entropy, or by a measure called the irreducible correlation. In this work, we show that the two measures coincide for states obeying an area law and having zero-correlation length. Moreover, we provide an operational meaning for these measures by proving its equivalence to the optimal rate of a particular class of secret sharing protocols.
This establishes an information-theoretical approach to multipartite correlations in topologically ordered systems.
Mehmet Burak Sahinoglu, Michael Walter and Dominic J. Williamson. A Tensor Network Framework for Topological Order in Higher Dimensions
K. R. Parthasarathy and Ritabrata Sengupta. Exchangeable Stationary and Entangled Chains of Gaussian States
Elizabeth Crosson and Aram Harrow. Rapidly mixing Monte Carlo for 1D stoquastic systems and simulated quantum annealing
Antonio Acin, Remigiusz Augusiak, Florian Curchod, Matty Hoban, Markus Johansson, Stefano Pironio, Tamas Vertesi and Peter Wittek. Certifying maximal randomness from a pair of entangled qubits
Nike Dattani, Richard Tanburn and Emile Okada. What is needed for a fully working adiabatic quantum computer to factor RSA-220 or to find a new Ramsey number?
Joseph M. Renes. Relative submajorization and its use in quantum resource theories
Felipe G. Lacerda, Joseph M. Renes and Volkher Scholz. Quantum polar coding for bosonic channels
Lídia Del Rio, Lea Kraemer and Renato Renner. Resource theories of knowledge
Emilio Onorati, Winton Brown, Oliver Buerschaper, Martin Kliesch, Albert Werner and Jens Eisert. Mixing properties of stochastic local Hamiltonians.
Random quantum processes play a central role both in the study of fundamental mixing processes in quantum mechanics related to equilibration, thermalisation and black hole scrambling, as well as in process design. In this work, we present a theory for continuous-time unitary evolutions originating from local Hamiltonians having time-fluctuating terms, reflecting a Brownian motion on the unitary group. By tying the mathematical description closely with the more established one of random quantum circuits, we present a unified picture for analyzing local random quantum processes. Much of the progress reported is of technical nature: in particular, by relying on representation theory, we analytically derive an expression for a local k-th moment operator that is entirely independent of k, giving rise to approximate unitary k-designs and quantum tensor product expanders. We also introduce tools for proving bounds on the rate of decoupling from an environment with random quantum processes.
Alex Parent, Martin Roetteler and Krysta Svore. Reversible circuit compilation with space constraints
Anand Natarajan, Aram Harrow and Xiaodi Wu. Limitations of monogamy, Tsirelsontype bounds, and other semidefinite programs in quantum information
Eugene Dumitrescu and Travis Humble. Direct Characterization of Quantum Dynamics with Noisy Ancilla
Chao-Hua Yu, Fei Gao, Qing-Le Wang and Qiao-Yan Wen. Quantum algorithm for association rules mining
Weiwei Zhang, Barry Sanders and David Feder. Topological signatures in two-dimensional continuous-time quantum walks
Cai Zhang and Haozhen Situ. Simultaneous dense coding with two-photon four-qubit cluster states
Haozhen Situ, Cai Zhang and Fang Yu. Quantum advice enhances social optimality in three-party conflicting interest games
Jinshi Xu, Kai Sun, Yongjian Han, Chuanfeng Li, Jiannis K. Pachos and Guangcan Guo. Simulation of non-Abelian characteristics of Majorana zero modes using a photonic quantum simulator
Sam Roberts and Stephen Bartlett. Symmetry protected topological order in the 3D cluster model
Peter Turner and Damian Markham. Derandomizing quantum circuits with measurement based unitary designs
Kosuke Fukui, Akihisa Tomita and Atsushi Okamoto. Proposal for quantum error correction with continuous variables
We study the robustness of the bucket brigade quantum random access memory model introduced by Giovannetti et al (2008 Phys. Rev. Lett.100 160501). Due to a result of Regev and Schiff (ICALP '08 733), we show that for a class of error models the error rate per gate in the bucket brigade quantum memory has to be of order $o({2}^{-n/2})$ (where $N={2}^{n}$ is the size of the memory) whenever the memory is used as an oracle for the quantum searching problem. We conjecture that this is the case for any realistic error model that will be encountered in practice, and that for algorithms with super-polynomially many oracle queries the error rate must be super-polynomially small, which further motivates the need for quantum error correction. By contrast, for algorithms such as matrix inversion Harrow et al (2009 Phys. Rev. Lett.103 150502) or quantum machine learning Rebentrost et al (2014 Phys. Rev. Lett.113 130503) that only require a polynomial number of queries, the error rate only needs to be polynomially small and quantum error correction may not be required. We introduce a circuit model for the quantum bucket brigade architecture and argue that quantum error correction for the circuit causes the quantum bucket brigade architecture to lose its primary advantage of a small number of 'active' gates, since all components have to be actively error corrected.
Daniel Brod. Classical simulation of extended matchgate circuits
Nadish de Silva. Strengths of Nonlocality and Contextuality: A Unified Approach
Debbie Leung and Nengkun Yu. Maximum privacy without coherence, zero-error
Robert Raussendorf, Nicolas Delfosse, Cihan Okay, Juan Bermejo-Vega and Dan E. Browne. Wigner function negativity and contextuality in quantum computation on qubits
Sebastian Grillo and Franklin De Lima Marquezino. A reformulation of the Quantum Query Model with a linear condition for exact algorithms
Go Kato, Kiyoshi Tamaki, Koji Azuma and Masaki Owari. Security of CV-QKD with transmitted local oscillator
Rafael Alexander and Nicolas Menicucci. Quantum computing with the quad-rail lattice
Yongsoo Hwang, Il Kwon Sohn and Jun Heo. Graph for a quantum graph code
Il Kwon Sohn, Yongsoo Hwang, Jeonghwan Shin and Jun Heo. Construction Scheme for Entanglement Assisted Quantum Codes using Graph
Libor Caha and Daniel Nagaj. Very entangled spin chains
Christoph Hirche and David Reeb. A Mrs. Gerber's Lemma with quantum side information
Christoph Hirche, Emili Bagan and John Calsamiglia. Asymptotic rates for minimum error discrimination with fixed measurements
Vincenzo Auletta, Diodato Ferraioli, Ashutosh Rai, Giannicola Scarpa and Andreas Winter. Belief Invariance: Nonsignalling Equilibria in Games with Conflicting Interest
Kohtaro Tadaki. A Refinement of Quantum Mechanics by Algorithmic Randomness
Shrobona Bagchi and Arun Kumar Pati. Uncertainty relations for general unitary operators
Adam Bookatz, Martin Roetteler and Pawel Wocjan. Improved bounded-strength decoupling schemes for local Hamiltonians
Open many-body quantum systems play an important role in quantum optics and condensed-matter physics, and capture phenomena like transport, interplay between Hamiltonian and incoherent dynamics, and topological order generated by dissipation. We introduce a versatile and practical method to numerically simulate one-dimensional open quantum many-body dynamics using tensor networks. It is based on representing mixed quantum states in a locally purified form, which guarantees that positivity is preserved at all times. Moreover, the approximation error is controlled with respect to the trace norm. Hence, this scheme overcomes various obstacles of the known numerical open-system evolution schemes. To exemplify the functioning of the approach, we study both stationary states and transient dissipative behaviour, for various open quantum systems ranging from few to many bodies.
Michael Frey. Faster state evolution with entanglement, measured by the Lee-Chau quantum speed limits
Tom Cooney, Jonathan Olson and Mark Wilde. On the complexity of the quantum recoverability problem
Joshua Lockhart and Simone Severini. Density matrices of grid-labeled graphs
Shun Kawakami, Toshihiko Sasaki and Masato Koashi. BB84 protocol with sequential phase encoding
Lucas Brady and Wim van Dam. Spectral Gap Analysis for Efficient Tunneling in Quantum Adiabatic Optimization
Yasuhito Kawano and Hiroshi Sekigawa. Quantum Algorithm for Lattice Problems
Nikolay Nahimov and Alexander Rivosh. Quantum walks on two-dimensional grids with multiple marked locations
Daniel Suess, Richard Kueng and David Gross. Certifying linear optical circuits via phaseless estimation techniques
Rafael Alexander, Pei Wang, Niranjan Sridhar, Moran Chen, Olivier Pfister and Nicolas Menicucci. One-way quantum computing with arbitrarily large time-frequency continuous-variable cluster states from a single optical parametric oscillator
Rafael Alexander, Natasha Gabay, Peter Rohde and Nicolas Menicucci. Modelling continuous-variable cluster states as variable interferometers with photon loss
Fumiaki Matsuoka and Akihisa Tomita. Entanglement Generation by Communication using Phase-Squeezed Light with Photon Loss
Marco Piani. Entanglement robustness provides the advantage in subchannel discrimination
Richard Tanburn, Oliver Lunt and Nike Dattani Dattani. Reducing runtimes in adiabatic quantum computation with Energy Landscape Manipulation (ELM)
We present a complete classification of all possible sets of classical reversible gates acting on bits, in terms of which reversible transformations they generate, assuming swaps and ancilla bits are available for free. Our classification can be seen as the reversible-computing analogue of Post’s lattice, a central result in mathematical logic from the 1940s. It is a step toward the ambitious goal of classifying all possible quantum gate sets acting on qubits. In fact, in the quantum setting, the affine classical gates appear as stabilizer gates, and we extend our classification of affine classical gates to give a complete classification of the stabilizer gates. Our theorem implies a linear-time algorithm, that takes as input the truth tables of reversible gates G and H and decides whether G generates H. Previously, this problem was not even known to be decidable. The theorem also implies that any n-bit reversible circuit can be “compressed” to an equivalent circuit, over the same gates, that uses at most 2^n poly(n) gates and O(1) ancilla bits; these are the first upper bounds on these quantities known, and are close to optimal. Finally, the theorem implies that every non-degenerate reversible gate can implement either every reversible transformation, or every affine transformation, when restricted to an “encoded subspace.” Briefly, the theorem says that every set of reversible gates generates either all reversible transformations on n-bit strings; no transformations; all transformations that preserve Hamming weight; all transformations that preserve Hamming weight mod k for some k; all affine transformations; all affine transformations that preserve Hamming weight mod 2 or mod 4, inner products mod 2, or a combination thereof; or a previous class augmented by a NOT or NOTNOT gate. Prior to this work, it was not even known that every class was finitely generated.
Shelby Kimmel and Yi-Kai Liu. Quantum Compressed Sensing Using 2-Designs
We develop a method for quantum process tomography that combines the efficiency of compressed sensing with the robustness of randomized benchmarking. Our method is robust to state preparation and measurement errors, and it achieves a quadratic speedup over conventional tomography when the unknown process is a generic unitary evolution. Our method is based on PhaseLift, a convex programming technique for phase retrieval. We show that this method achieves approximate recovery of almost all signals, using measurements sampled from spherical or unitary 2-designs. This is the first positive result on PhaseLift using 2-designs. We also show that exact recovery of all signals is possible using unitary 4-designs. Previous positive results for PhaseLift required spherical 4-designs, while PhaseLift was known to fail in certain cases when using spherical 2-designs.
Mark Girard and Gilad Gour. Entanglement conversion witness