 |
|
||||
- JIANXIN CHEN, University of Guelph/University of Waterloo
Universal Entangler Revisited [PDF]
-
We will introduce the concept of universal entangler, which is a gate transforms all product states to entangled states. In practice, a universal entangler is a very powerful device for generating entanglements, and thus provides important physical resources for accomplishing many tasks in quantum computing and quantum information. We will show that except for some degenerate cases, the universal entangler always exists. Furthermore, such "universal entangling power" is a generic property for quantum gates. Then we will generalize our results to multipartite systems.
- ANDREW CHILDS, University of Waterloo
The quantum query complexity of read-many formulas [PDF]
-
The quantum query complexity of evaluating any read-once formula with n black-box input bits is $\Theta(\sqrt n)$. However, the corresponding problem for read-many formulas (i.e., formulas in which the inputs have fanout) is not well understood. Although the optimal read-once formula evaluation algorithm can be applied to any formula, it can be suboptimal if the inputs have large fanout. We give an algorithm for evaluating any formula with $n$ inputs, size $S$, and $G$ gates using $O(\min\{n, \sqrt S, n^{1/2} G^{1/4}\})$ quantum queries. Furthermore, we show that this algorithm is optimal, since for any $n,S,G$ there exists a formula with $n$ inputs, size at most $S$, and at most $G$ gates that requires $\Omega(\min\{n, \sqrt S, n^{1/2} G^{1/4}\})$ queries. We also show that the algorithm remains nearly optimal for circuits of any particular depth of at least 3, and we give a linear-size circuit of depth 2 that requires $\Omega(n^{0.555})$ queries. Applications of these results include an $\Omega(n^{1.055})$ lower bound for Boolean matrix product verification, a nearly tight characterization of the quantum query complexity of evaluating constant-depth circuits with bounded fanout, new formula gate count lower bounds for several functions including parity, and a construction of an $\mathrm{AC}^0$ circuit of linear size that can only be evaluated by a formula with $\Omega(n^{2-\epsilon})$ gates.
Based on joint work with Shelby Kimmel and Robin Kothari.
- ROGER COLBECK, Perimeter Institute
New insights into uncertainty relations [PDF]
-
Uncertainty relations provide bounds on how well we can predict the outcomes of two incompatible measurements, such as position and momentum, on a particle. I will describe a recent extension of such relations which incorporate quantum side information, and outline a new proof, showing that they arise as the result of a few simple entropic properties.
- SARAH CROKE, Perimeter Institute
The power of $O(1)$ qubits: perfect state discrimination with tiny quantum computers [PDF]
-
In this paper, we show that quantum information processors (QIPs) with $O(1)$ qubits can substantially reduce measurement complexity – i.e., the number of samples required to learn something about an unknown quantum state. We present tiny-QIP algorithms that:
1. use a $\log_2 K$-qubit QIP to discriminate optimally between $K$ $N$-copy pure states $|\psi_k \rangle^{\otimes N}$, which is \textit{not} known to be achievable with local measurements.
2. use a $\log_2(KD)$-qubit QIP to discriminate optimally between $K$ $N$-site matrix product states with bond dimension $D$, achieving an $O(N)$ improvement over local tomography.
These protocols demonstrate useful applications for the 2-14 qubit QIPs that exist today. Such QIPs are computationally trivial (their dynamics can be easily simulated on classical computers), but our results suggest nontrivial applications in sensing, detection, metrology, and characterization of larger prototype QIPs.
Joint work with Robin Blume-Kohout and Michael Zwolak.
- GUS GUTOSKI, Institute for Quantum Computing, University of Waterloo
On a measure of distance for quantum strategies [PDF]
-
The present paper studies an operator norm that captures the distinguishability of quantum strategies in the same sense that the trace norm captures the distinguishability of quantum states or the diamond norm captures the distinguishability of quantum channels.
Characterizations of its unit ball and dual norm are established via strong duality of a semidefinite optimization problem.
This norm and its properties are employed to generalize a state discrimination result of arXiv:cs/0412102v1 [cs.CC].
The generalized result states that for any two convex sets $S,T$ of strategies there exists a fixed interactive measurement scheme that successfully distinguishes any choice of $s\in S$ from any choice of $t\in T$ with bias proportional to the minimal distance between the sets $S$ and $T$ as measured by this norm.
A similar discrimination result for channels then follows as a special case.
- ZHENGFENG JI, University of Waterloo
Correlations in excited states of local Hamiltonians [PDF]
-
Physical properties of the ground and excited states of a $k$-local Hamiltonian are largely determined by the $k$-particle reduced density matrices ($k$-RDMs), or simply the $k$-matrix for fermionic systems---they are at least enough for the calculation of the ground state and excited state energies. Moreover, for a non-degenerate ground state of a $k$-local Hamiltonian, even the state itself is completely determined by its $k$-RDMs, and therefore contains no genuine ${>}k$-particle correlations, as they can be inferred from $k$-particle correlation functions. It is natural to ask whether a similar result holds for non-degenerate excited states. In fact, for fermionic systems, it has been conjectured that any non-degenerate excited state of a 2-local Hamiltonian is simultaneously a unique ground state of another 2-local Hamiltonian, hence is uniquely determined by its 2-matrix. And a weaker version of this conjecture states that any non-degenerate excited state of a 2-local Hamiltonian is uniquely determined by its 2-matrix among all the pure $n$-particle states. We construct explicit counterexamples to show that both conjectures are false. It means that correlations in excited states of local Hamiltonians could be dramatically different from those in ground states. We further show that any non-degenerate excited state of a $k$-local Hamiltonian is a unique ground state of another $2k$-local Hamiltonian, hence is uniquely determined by its $2k$-RDMs (or $2k$-matrix).
- NATHANIEL JOHNSTON, University of Guelph
Adjoint-Invariance and Complete Positivity in Quantum Information Theory [PDF]
-
We investigate the types of cones that can arise as completely positive maps between abstract operator systems on complex matrices. To every cone with a property that we call right-adjoint-invariance there is an associated operator system, and furthermore the associated operator system is unique. Conversely, the cone of completely positive maps on any operator system is right-adjoint-invariant cone. Several cones of linear maps satisfy this right-adjoint-invariance property and are thus completely positive between certain operator systems. We will explore several examples, such as the cones of $k$-positive and $k$-entanglement breaking maps, the cones of anti-degradable maps and $k$-local broadcasting maps, and the cone of local entanglement-annihilating maps.
- DEBBIE LEUNG, Institute for Quantum Computing
Finite amount of entanglement can be insufficient for a small size quantum game [PDF]
-
We define the notion of coherent state exchange and provide a solution for any number of parties.
We obtain the following applications: (1) The set of entanglement-assisted local operations is shown not to be a closed set. (2) There exists a game in which two provers who cannot communicate with one another cannot implement an optimal winning strategy with finite amount of shared entanglement. The game consists of only one quantum message of low dimension from a referee to each of the provers and vice versa. Consequently, there is no general bound in the entanglement required in quantum multi-party interactive proof system. (3) A simple proof that any multi-prover quantum interactive proof system can be efficiently transformed to have near-perfect completeness. Joint work with Ben Toner and John Watrous.
- MARCO PIANI, IQC and Department of Physics and Astronomy, University of Wateloo
Quantumness and entanglement in quantum measurements [PDF]
-
Given a multipartite system, we study the entanglement established between the system and a set of measurement apparata used to perform local complete projective measurements. We prove that distillable entanglement is necessarily created by the measurement interaction unless the correlations between the subsystems to be measured are strictly classical. We thus quantify the amount of \emph{quantumness of correlations} between the original subsystems by the minimum entanglement necessarily established in such an interaction. We prove that the quantumness so quantified is always greater than the entanglement between the original subsystems, independently of the measure of entanglement used. We apply our approach and results to the analysis of the spreading of (multipartite) entanglement and quantumness along a von Neumann chain.
- SARAH PLOSKER, University of Guelph
Private Quantum Channels, Conditional Expectations, and Trace Vectors [PDF]
-
We first briefly review private quantum channels (PQCs), conditional expectations, and trace vectors. We provide a new characterization of single qubit PQCs by considering the Bloch sphere. We introduce trace preserving conditional expectations, which we call conditional expectation channels, and show that a conditional expectation channel is a PQC if and only if the subset on which it is defined is a set of trace vectors for the algebra. Joint work by Amber Church, David W. Kribs, and Rajesh Pereira.
- AIDAN ROY, University of Waterloo
Uniform mixing in distance-regular graphs [PDF]
-
In 2001, Moore and Russell showed that the hypercube demonstrates exact uniform mixing: it has a continuous-time quantum walk that not only mixes faster than a classical random walk but also has a distribution which is perfectly uniform across all vertices. While quantum walks have proven to be applicable to a variety of other graphs, the problem of determining which graphs exhibit exact uniform mixing has not been resolved and appears to be of independent combinatorial interest.
In this talk, we show that two of the more obvious candidate classes of highly structured graphs do not exhibit exact uniform mixing. In particular, there is no uniform mixing in strongly-regular graphs with more than 4 vertices, and the only antipodal distance-regular graph of diameter 3 that exhibits uniform mixing is the 3-cube. These observations follow from some new combinatorial results about type-II matrices in association schemes.
This is joint work with Ada Chan.
- JOHN WATROUS, Institute for Quantum Computing, University of Waterloo
Hedging bets with correlated quantum strategies [PDF]
-
In this work, we consider correlations among independently administered hypothetical tests of a simple interactive type, and demonstrate that correlations arising in quantum information theoretic variants of these tests can exhibit a striking non-classical behavior. When viewed in a game-theoretic setting, these correlations are suggestive of a perfect form of hedging, where the risk of a loss in one game of chance is perfectly offset by one’s actions in a second game. This type of perfect hedging is quantum in nature: it is not possible in classical variants of the tests we consider.
Based on joint work with Abel Molina.
