QIP 2016 Scientific Program

Connections between quantum theories violation of formal notions of classicality and its information processing advantages have been studied, shedding new light on both. But since the latter are only relevant to the real world if they are robust to imperfect realisations, it is important for this line of work that the notions of classicality are similarly robust. Local causality meets the condition, but does noncontextuality? This talk will outline our solutions to two apparent failures of robustness for noncontextuality: the first being the apparent requirement of exact operational equivalences between distinct procedures, and the second being that many proofs of contextuality call for measurements that are projective. Both of these are addressed without any change to Spekkens' operational definition of contextuality, instead we rely on better use of the structure of probabilistic theories, in particular convex combinations. This structure turns out to already provide the necessary ``continuity'' to deal with imperfect realizations. The talk will also mention our experimental refutation of noncontextuality that builds on these ideas. Time permitting, the talk will end with some speculation on how these ideas could enable cryptography that doesn't assume all of quantum theory, even in a prepare-and-measure scenario. This highlights that noncontextuality can be applied in scenarios where local causality is simply not relevant.

http://arxiv.org/abs/1505.06244

We present a classical interactive protocol that verifies the validity of a quantum witness state for the local Hamiltonian problem. It follows from this protocol that approximating the non-local value of a multi-player one-round game to inverse polynomial precision is QMA-hard. Our work makes an interesting connection between the theory of QMA-completeness and Hamiltonian complexity on one hand and the study of non-local games and Bell inequalities on the other.

http://arxiv.org/abs/1505.07432

The class $\MIP^*$ of promise problems that can be decided through an interactive proof system with multiple entangled provers provides a complexity-theoretic framework for the exploration of the nonlocal properties of entanglement. Very little is known in terms of the power of this class. The only proposed approach for establishing upper bounds is based on a hierarchy of semidefinite programs introduced independently by Pironio et al. and Doherty et al. in 2006. This hierarchy converges to a value, the field-theoretic value, that is only known to coincide with the provers' maximum success probability in a given proof system under a plausible but difficult mathematical conjecture, Connes' embedding conjecture. No bounds on the rate of convergence are known. We introduce a rounding scheme for the hierarchy, establishing that any solution to its $N$-th level can be mapped to a strategy for the provers in which measurement operators associated with distinct provers have pairwise commutator bounded by $O(\ell^2/\sqrt{N})$ in operator norm, where $\ell$ is the number of possible answers per prover. Our rounding scheme motivates the introduction of a variant of quantum multiprover interactive proof systems, called $\MIP_\delta^*$, in which the soundness property is required to hold against provers allowed to operate on the {same} Hilbert space as long as the commutator of operations performed by distinct provers has norm at most $\delta$. Our rounding scheme implies the upper bound $\MIP_\delta^* \subseteq \DTIME(\exp(\exp (\poly)/\delta^2))$. In terms of lower bounds we establish that $\MIP^*_{2^{- \poly}}$, with completeness $1$ and soundness $1-2^{-\poly}$, contains $\NEXP$. The relationship of $\MIP_\delta^*$ to $\MIPstar$ has connections with the mathematical literature on approximate commutation. Our rounding scheme gives an elementary proof that the Strong Kirchberg Conjecture implies that $\MIP^*$ is computable. We also discuss applications to device-independent cryptography.

http://arxiv.org/pdf/1510.00102v1.pdf

The well-known Horodecki criterion asserts that a state $\rho$ on $C^d \otimes C^d$ is entangled if and only if there exists a positivity-preserving map $\Phi : M_d \to M_d$ such that the operator $(\Phi \otimes Id)(\rho)$ is not positive semi-definite. We show that that the number of such maps needed to detect all the robustly entangled states (i.e., states $\rho$ which remain entangled even in the presence of substantial randomizing noise) exceeds $\exp(c d^3 / \log d)$. The proof is based on a study of the approximability of the set of states (resp. of separable states) by polytopes with few vertices or with few faces, and ultimately relies on the Dvoretzky--Milman theorem about the dimension of almost spherical sections of convex bodies. The result can be interpreted as a geometrical manifestation of the complexity of entanglement detection.

http://arxiv.org/abs/1510.00578v1

We show a number of new separations between various query complexity measures, including: 1. A function f for which the bounded error quantum query complexity, $Q (f)$ is, up to logarithmic factors, equal to $D^{1/4}(f)$ (where $D(f)$ is the deterministic query complexity of $f$). This is the first improvement over the quadratic gap between $Q(f)$ and $D(f)$ provided by Grover's algorithm. 2. A function f for which the exact quantum query complexity $Q_E(f)$ is, up to logarithmic factors, equal to $(R_0(f))^{2/3}$ where $R_0$ is the zero-error randomized complexity of $f$. Previously, the biggest gap was $Q_E(f)=O(R_0(f)^ {0.86...}$) by Ambainis (STOC'2013). 3. A function f for which the zero-error randomized complexity $R_0(f)$ is, up to logarithmic factors, equal to $(D(f))^{1/2}$. This is a seperation between two complexity measures which are both classical but it provides an improvement for a question where the previous best separation ($R_0(f)=O(D (f)^{0.753...}$) was shown in 1986. All of our examples are based on a function recently introduced by Goos, Pitassi, and Watson to separate the unambiguous nondeterministic query complexity from deterministic query complexity and which was used to resolve the famous Clique vs. Independent Set problem in communication complexity.

http://arxiv.org/abs/1506.04719

Harrow, Hassidim, and Lloyd showed that for a suitably specified N×N matrix A and N-dimensional vector b, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations Ax=b. If A is sparse and well-conditioned, their algorithm runs in time poly (log N, 1/ε), where ε is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in log(1/ε), exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on ε is prohibitive.

http://arxiv.org/abs/1511.02306

In this talk I will describe a general method to obtain quantum speedups of classical algorithms which are based on the technique of backtracking, a standard approach for solving constraint satisfaction problems (CSPs). Backtracking algorithms explore a tree whose vertices are partial solutions to a CSP in an attempt to find a complete solution. Assume there is a classical backtracking algorithm which finds a solution to a CSP on n variables, or outputs that none exists, and whose corresponding tree contains T vertices, each vertex corresponding to a test of a partial solution. I will show that there is a bounded-error quantum algorithm which completes the same task using O (sqrt(T) n^(3/2) log n) tests. In particular, this quantum algorithm can be used to speed up the DPLL algorithm, which is the basis of many of the most efficient SAT solvers used in practice. The quantum algorithm is based on the use of a quantum walk algorithm of Belovs to search in the backtracking tree.

http://arxiv.org/abs/1509.02374

The Boolean constraint satisfaction problem 3-SAT is arguably the canonical NP-complete problem. In contrast, 2-SAT can not only be decided in polynomial time, but in fact in deterministic linear time. In 2006, Bravyi proposed a physically motivated generalization of k-SAT to the quantum setting, defining the problem "quantum k-SAT". He showed that quantum 2-SAT is also solvable in polynomial time on a classical computer, in particular in deterministic time O(n^4), assuming unit-cost arithmetic over a field extension of the rational numbers, where n is number of variables. In this paper, we present an algorithm for quantum 2-SAT which runs in linear time, i.e. deterministic time O(n+m) for n and m the number of variables and clauses, respectively. Our approach exploits the transfer matrix techniques of Laumann et al. [QIC, 2010] used in the study of phase transitions for random quantum 2-SAT, and bears similarities with both the linear time 2- SAT algorithms of Even, Itai, and Shamir (based on backtracking) [SICOMP, 1976] and Aspvall, Plass, and Tarjan (based on strongly connected components) [IPL, 1979].

http://arxiv.org/abs/1508.07338

A canonical result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, we are given a family of 2-qubit projectors $\Pi_{ij}$ on a system of $n$ qubits, and the task is to decide whether the Hamiltonian $H=\sum \Pi_{ij}$ has a 0-eigenvalue, or it is larger than $1/n^\alpha$ for some $\alpha=O(1)$. The problem is not only a natural extension of the classical 2-SAT problem to the quantum case, but is also equivalent to the problem of finding the ground state of 2-local frustration-free Hamiltonians of spin $\frac{1}{2}$, a well-studied model believed to capture certain key properties in modern condensed matter physics. While Bravyi has shown that the quantum 2-SAT problem has a classical polynomial-time algorithm, the running time of his algorithm is $O(n^4)$. In this paper we give a classical algorithm with linear running time in the number of local projectors, therefore achieving the best possible complexity.

http://arxiv.org/pdf/1508.06340v1

We propose a novel tensor network construction of quantum error-correcting codes inspired by properties of the celebrated holographic correspondence. Our building block is a special family of tensors with multiple indices of equal dimension and admitting a unitary interpretation for any balanced index bipartition. By properly identifying uncontracted indices as input or output, the entire tensor network can be interpreted as an isometry, an encoding map for a quantum error-correcting code. The resulting isometry captures key features of the holographic (bulk/boundary) correspondence. In particular, we provide a systematic procedure for representing logical operators on specific subsets of physical qubits which we call the greedy reconstruction algorithm. This procedure, mimics the Rindler-wedge reconstruction present in holography and explicitly realizes the connection with quantum codes proposed by Almheiri et al.. Furthermore, by interpreting the graph structure of a tensor network as a discrete geometry, we make contact with a holographic statement due to Ryu and Takayanagi relating entanglement with minimal surfaces. Namely, under simple graph theoretic assumptions, we prove a max-flow/min-cut statement by which the entanglement of a sub-region is equal to the minimal number of cuts needed to disconnect the region from its complement. The proposed framework provides a flexible way to design novel quantum codes, allows explicitly realizing tailored entanglement structures.

http://arxiv.org/abs/1503.06237

Combining protection from noise and computational universality is one of the biggest challenges in the fault-tolerant quantum computing. Topological stabilizer codes such as the 2D surface code can tolerate a high level of noise but implementing logical gates, especially non-Clifford ones, requires a prohibitively large overhead due to the need of state distillation. In this talk I will describe a new family of 2D quantum error correcting codes that enables a transversal implementation of all logical gates required for the universal quantum computing. Transversal logical gates (TLG) are encoded operations that can be realized by applying some single- qubit rotation to each physical qubit. TLG are highly desirable since they introduce no overhead and do not spread errors. It has been known before that a quantum code can have only a finite number of TLGs which rules out computational universality. Our scheme circumvents this no-go result by combining TLGs of two different quantum codes using the gauge-fixing method pioneered by Paetznick and Reichardt. The first code, closely related to the 2D color code, enables a transversal implementation of all single-qubit Clifford gates. The second code that we call a doubled color code provides a transversal T-gate The Clifford+T gate set is known to be computationally universal. The two codes can be laid out on the honeycomb lattice with two qubits per site such that the code conversion requires parity measurements for six-qubit Pauli operators supported on faces of the lattice. I will also describe numerical simulations of logical Clifford+T circuits encoded by the distance-3 doubled color code.

http://arxiv.org/abs/1509.03239

We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using a property-testing problem called Forrelation, where one needs to decide whether one Boolean function is highly correlated with the Fourier transform of a second function. This problem can be solved using 1 quantum query, yet we show that any randomized algorithm needs \Omega(\sqrt{N}/log N) queries (improving an \Omega(N^{1/4}) lower bound of Aaronson). Conversely, we show that this 1 versus \tilde{\Omega}(\sqrt{N}) separation is optimal: indeed, any t-query quantum algorithm whatsoever can be simulated by an O\left(N^{1- 1/2t}\right)-query randomized algorithm. Thus, resolving an open question of Buhrman et al. from 2002, there is no partial Boolean function whose quantum query complexity is constant and whose randomized query complexity is linear. We conjecture that a natural generalization of Forrelation achieves the optimal t versus \Omega(N^{1-1/2t}) separation for all t. As a bonus, we show that this generalization is BQP-complete. This gives a second sense in which Forrelation "captures the maximum power of quantum computation".

http://arxiv.org/abs/1411.5729

We consider the problem of testing multiple quantum hypotheses $\{\rho_1^ {\otimes n},\ldots,\rho_r^{\otimes n}\}$, where an arbitrary prior distribution is given and each of the $r$ hypotheses is $n$ copies of a quantum state. It is known that the minimal average error probability $P_e$ decays exponentially to zero, that is, $P_e\thicksim\exp(-\xi n)$. However, this error exponent $\xi$ is generally unknown, except for the case that $r=2$. In this paper, we solve the long-standing open problem of identifying the above error exponent, by proving Nussbaum and Szko{\l}a's conjecture that $\xi=\min_{i\neq j}C(\rho_i, \rho_j)$. The right-hand side of this equality is called the multiple quantum Chernoff distance, and $C(\rho_i,\rho_j):= \max_{0\leq s\leq 1}\{-\log\tr\rho_i^s\rho_j^{1-s}\}$ has been previously identified as the optimal error exponent for testing two hypotheses, $ \rho_i^{\otimes n}$ versus $\rho_j^ {\otimes n}$. The main ingredient of our proof is a new upper bound for the average error probability, for testing an ensemble of finite-dimensional, but otherwise general, quantum states. This upper bound, up to a states-dependent factor, matches the multiple-state generalization of Nussbaum and Szko{\l}a's lower bound. Specialized to the case $r=2$, we give an alternative proof to the achievability of the binary-hypothesis Chernoff distance, which was originally proved by Audenaert et al.

http://arxiv.org/abs/1508.06624

We classify two-qubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a two-qubit commuting Hamiltonian H which one can apply to any pair of qubits, starting in a computational basis state. We prove a dichotomy theorem: either this model is efficiently classically simulable or it allows us to sample from probability distributions which cannot be sampled from classically unless the polynomial hierarchy collapses. Furthermore, the only simulable Hamiltonians are those which fail to generate entanglement. This shows that generic two-qubit commuting Hamiltonians can be used to perform computational tasks which are intractable for classical computers under plausible assumptions. Our proof makes use of a structure theorem for commuting Hamiltonians, new postselection gadgets, and Lie theory.

http://people.csail.mit.edu/adam/Papers/commuting_hamiltonians.pdf

A state on a tripartite quantum system ABC forms a Markov chain if it can be reconstructed from its marginal on AB by a quantum operation from B to BC. We show that the quantum conditional mutual information I(A:C|B) of an arbitrary state is an upper bound on its distance to the closest reconstructed state. It thus quantifies how well the Markov chain property is approximated.

http://arxiv.org/abs/1410.0664

The fact that the quantum relative entropy is non- increasing with respect to quantum physical evolutions lies at the core of many optimality theorems in quantum information theory and has applications in other areas of physics. In this work, we establish improvements of this entropy inequality in the form of physically meaningful remainder terms. One of the main results can be summarized informally as follows: if the decrease in quantum relative entropy between two quantum states after a quantum physical evolution is relatively small, then it is possible to perform a recovery operation that only depends on the physical evolution and the second quantum state, such that one can perfectly recover the second state while approximately recovering the first state. This can be interpreted as quantifying how well one can reverse a quantum physical evolution. Furthermore, we prove that the recovery operation has an explicit structure satisfying a universality property in the sense that it is independent from the state that is approximately recovered. Our proof method is elementary, relying on complex interpolation, basic linear algebra, and the recently introduced Renyi generalization of a relative entropy difference. The theorem has a number of applications in quantum information theory, which have to do with providing physically meaningful improvements to many known entropy inequalities.

http://arxiv.org/abs/1504.07251
http://arxiv.org/abs/1505.04661
http://arxiv.org/abs/1509.07127

Complex information-processing systems, for example quantum circuits, cryptographic protocols, or multi-player games, are naturally described as networks composed of more basic information-processing systems. A modular analysis of such systems requires a mathematical model of systems that is closed under composition, i.e., a network of these objects is again an object of the same type. We propose such a model and call the corresponding systems causal boxes. Causal boxes capture superpositions of causal structures, e.g., messages sent by a causal box A can be in a superposition of different orders or in a superposition of being sent to box B and box C. Furthermore, causal boxes can model systems whose behavior depends on time. By instantiating the Abstract Cryptography framework with causal boxes, we obtain the first composable security framework that can handle arbitrary quantum protocols and relativistic protocols.

http://arxiv.org/abs/1512.02240

Fully homomorphic encryption is an encryption method with the property that any computation on the plaintext can be performed by a party having access to the ciphertext only. Here, we formally define and give schemes for quantum homomorphic encryption, which is the encryption of quantum information such that quantum computations can be performed given the ciphertext only. Our schemes allows for arbitrary Clifford group gates, but become inefficient for circuits with large complexity, measured in terms of the non-Clifford portion of the circuit (we use the "pi/8" non-Clifford group gate, which is also known as the T-gate). More specifically, two schemes are proposed: the first scheme has a decryption procedure whose complexity scales with the square of the number of T-gates (compared with a trivial scheme in which the complexity scales with the total number of gates); the second scheme uses a quantum evaluation key of length given by a polynomial of degree exponential in the circuit's T-gate depth, yielding a homomorphic scheme for quantum circuits with constant T-depth. Both schemes build on a classical fully homomorphic encryption scheme. A further contribution of ours is to formally define the security of encryption schemes for quantum messages: we define quantum indistinguishability under chosen plaintext attacks in both the public and private- key settings. In this context, we show the equivalence of several definitions. Our schemes are the first of their kind that are secure under modern cryptographic definitions, and can be seen as a quantum analogue of classical results establishing homomorphic encryption for circuits with a limited number of multiplication gates. Historically, such results appeared as precursors to the breakthrough result establishing classical fully homomorphic encryption.

http://arxiv.org/abs/1412.8766

Two major open problems regarding the parallel repetition of multiplayer games are whether an analogue of Raz's parallel-repetition theorem holds for (a) games with more than two players, and (b) games with quantum players using entanglement. We make progress on these problems: we introduce a class of games we call "anchored", and then prove exponential-decay parallel repetition theorems for anchored games in the multiplayer and entangled- player settings. We then introduce a simple transformation on games called "anchoring", inspired in part by the Feige-Kilian transformation [SICOMP '00], and show that this transformation turns any (multiplayer) game into an anchored game. Together, our parallel repetition theorem and our anchoring transformation provide a simple and efficient hardness- amplification technique for general games with multiple players or with quantum players. Our anchoring transformation allows us to circumvent the need to employ the correlated sampling technique, and thus provide a way to avoid the primary obstruction to proving hardness amplification results for general games beyond the classical two-player setting.

http://arxiv.org/abs/1509.07466

We prove a near optimal round-communication tradeoff for the two-party quantum communication complexity of disjointness. For protocols with r rounds, we prove a lower bound of tilde{Omega}(n/r + r) on the communication required for computing disjointness of input size n, which is optimal up to logarithmic factors. The previous best lower bound was Omega(n/r^2 + r) due to Jain, Radhakrishnan and Sen. Along the way, we develop several tools for quantum information complexity, one of which is a lower bound for quantum information complexity in terms of the generalized discrepancy method. As a corollary, we get that the quantum communication complexity of any boolean function f is at most 2^{O(QIC(f))}, where QIC(f) is the prior-free quantum information complexity of f (with error 1/3).

http://eccc.hpi- web.de/report/2015/081/

Degradable quantum channels are an important class of completely positive trace-preserving maps. Among other properties, they offer a single-letter formula for the quantum and the private classical capacity and are characterized by the fact that the complementary channel can be obtained from the channel by applying a degrading map. In this work we introduce the concept of approximate degradable channels, which satisfy this condition up to some finite $\varepsilon \geq 0$. That is, there exists a degrading map which upon composition with the channel is $\varepsilon$- close in the diamond norm to the complementary channel. We show that for any fixed channel the smallest such $\varepsilon$ can be efficiently determined via a semidefinite program. Moreover, these approximate degradable channels also approximately inherit all other properties of degradable channels. As an application, we derive improved upper bounds to the quantum and private classical capacity for certain channels of interest in quantum communication.

http://arxiv.org/abs/1412.0980

In the k-junta testing problem, a tester has to efficiently decide whether a given function f:{0,1}^n → {0,1} is a k-junta (i.e., depends on at most k of its input bits) or is ε-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity O(sqrt{k/ε}) and time complexity O(n*sqrt{k/ε}). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atici and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic (4th power) improvement over the query complexity of the best classical algorithm. (The 4th power quantum advantage is a bit unusual - most of quantum algorithms are either exponentially better than classical or at most quadratically better.) To show that our algorithm can be implemented time-efficiently, we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of O(k^{1/3}) queries for junta- testing (for constant ε).

http://arxiv.org/abs/1507.03126

We prove a lower bound to the spectral gap of the Davies generator for general N - qubit commuting Pauli Hamiltonians and for quantum doubles based on an Abelian group. We derive rigorous thermalization time bounds, also called mixing time bounds, for the Davies generators of these Hamiltonians. Davies generators are given in the form of a Lindblad equation and are known to converge to the Gibbs distribution of the particular Hamiltonian for which they are derived. The bound on the spectral gap essentially depends on a single number E referred to as the generalized energy barrier. When any local defect can be grown into a logical operator and in turn any product operator can be decomposed into a product of the clusters of such incomplete logical operators, then E corresponds to the largest energy barrier of the canonical logical operators. The main conclusion that can be drawn from our result is, that the presence of an energy barrier for the logical operators is in fact, although not sufficient, a necessary condition for a thermally stable quantum memory when we assume the full Davies dynamics as noise model. This rules out the possibility of entropic protection for this broad group of models.

http://arxiv.org/abs/1412.2858
http://arxiv.org/abs/1601.01324

We present an algorithm for efficient approximation of unitaries using gate sets based on totally definite quaternion algebras. It approximates unitaries within precision ε using circuits of length O(log(1/ε)) which is asymptotically optimal. The algorithm achieves the same quality of approximation as previously known algorithms for Clifford+T [arXiv:1212.6253], V-basis [arXiv:1303.1411] and Clifford+π/12 [arXiv:1409.3552] and runs on average in time polynomial in log(1/ε) (conditional on a number-theoretic conjecture). Our algorithm is the first algorithm with described properties that works for a wide range of gate sets.

http://arxiv.org/abs/1504.04350
http://arxiv.org/abs/1510.03888

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.

http://arxiv.org/abs/1504.07999

The topological color code and the toric code are two leading candidates for realizing fault-tolerant quantum computation. Here we show that the color code on a d-dimensional closed manifold is equivalent to multiple decoupled copies of the d-dimensional toric code up to local unitary transformations and adding or removing ancilla qubits. Our result not only generalizes the proven equivalence for d=2, but also provides an explicit recipe of how to decouple independent components of the color code, highlighting the importance of colorability in the construction of the code. Moreover, for the d-dimensional color code with d+1 boundaries of d+1 distinct colors, we find that the code is equivalent to multiple copies of the d-dimensional toric code which are attached along a (d-1)-dimensional boundary. In particular, for d=2, we show that the (triangular) color code with boundaries is equivalent to the (folded) toric code with boundaries. We also find that the d-dimensional toric code admits logical non-Pauli gates from the d-th level of the Clifford hierarchy, and thus saturates the bound by Bravyi and Koenig. In particular, we show that the d-qubit control-Z logical gate can be fault-tolerantly implemented on the stack of d copies of the toric code by a local unitary transformation.

http://arxiv.org/abs/1503.02065

We present several polynomial- and quasipolynomial-time approximation schemes for a large class of generalized operator norms. Special cases include the 2-> q norm of matrices for q>2, the support function of the set of separable quantum states, finding the least noisy output of entanglement- breaking quantum channels, and approximating the injective tensor norm for a map between two Banach spaces whose factorization norm through ell_1^n is bounded. These reproduce and in some cases improve upon the performance of previous algorithms by Brandao-Christandl-Yard and followup work, which were based on the Sum-of-Squares hierarchy and whose analysis used techniques from quantum information such as the monogamy principle of entanglement. Our algorithms, by contrast, are based on brute force enumeration over carefully chosen covering nets. These have the advantage of using less memory, having much simpler proofs and giving new geometric insights into the problem. Net-based algorithms for similar problems were also presented by Shi-Wu and Barak-Kelner-Steurer, but in each case with a run-time that is exponential in the rank of some matrix. We achieve polynomial or quasipolynomial runtimes by using the much smaller nets that exist in ell_1 spaces. This principle has been used in learning theory, where it is known as Maurey's empirical method.

http://arxiv.org/abs/1509.05065

https://sites.google.com/site/marcotomch/QIP16_finite_resources.pdf

Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered and the security of only some types of extractors was shown.

http://arxiv.org/abs/1510.06743

In this work, we study the entropies of holographic quantum systems (that is, states of strongly coupled quantum field theories that admit a dual gravitational description). We show that, surprisingly, the study of holographic entropies can be reduced to combinatorics: an entropy inequality is valid for holographic systems if and only if it holds for the min-­cuts in an arbitrary graph. We discuss several consequences, one of which is a purely combinatorial proof technique that allows us to obtain an infinite family of new holographic entropy inequalities, generalizing the previously known ones. By systematically studying the holographic entropy cone, which parametrizes the region of allowed entropies, we also obtain new insights into the relationship between entropies in holographic systems and other quantum mechanical systems.

http://arxiv.org/abs/1505.07839

In this work, we describe an experimentally feasible small-scale physical device, which uses n copies of an unknown quantum state to estimate the state's spectrum. The well-known efficient quantum algorithm for this task utilizes the quantum Schur transform. Implementing such an algorithm in the usual way would require a scalable, universal circuit-model quantum computer. Our protocol, on the other hand, involves Ramsey spectroscopy of fermionic alkaline-earth atoms in a square-well trap, and should be experimentally realizable with current technology. Much like the analogous quantum algorithm, our protocol effectively implements a measurement in the Schur basis. The Schur transform maps the computational basis of n qudits to the Schur basis, which consists of matrix entries of irreducible representations of S_n \times SU(d). The aforementioned efficient quantum algorithm (polynomial in n and d) for implementing the Schur transform was first given by Bacon, Chuang and Harrow, along with a number of applications. Among these are optimal spectrum estimation, universal entanglement concentration, encoding into decoherence-free subsystems, optimal hypothesis testing and quantum and classical communication without shared reference frames. We show that our physical system is well-suited for spectrum estimation; adapting it to the other applications is an open problem.

The Wigner function and Clifford group play fundamental roles in physics and quantum information science. Many desirable properties of the Wigner function are intimately connected to the high symmetry of the underlying operator basis composed of phase point operators. In each odd prime power dimension, this phase point basis is covariant with respect to the Clifford group. When the dimension is a power of 2, it is believed that no such basis can exist; however, no rigorous proof is known before despite the significance of this problem and intensive efforts of many researchers in the last three decades. We prove that in each odd prime power dimension, the phase point basis is the unique operator basis up to scaling that is covariant with respect to the Clifford group, while no such basis can exist when the dimension is a power of 2. In addition, the phase point basis is almost uniquely determined by the double transitivity of its symmetry group, that is, any pair of phase point operators can be transformed to any other pair by a unitary transformation in the symmetry group. Furthermore, we prove that the multiqubit Clifford group is a unitary 3-design and no operator basis can be covariant with respect to a unitary 3-design, thereby providing a simple explanation of why no discrete Wigner function is covariant with respect to the multiqubit Clifford group. As another implication, any orbit of pure states of the Clifford group forms a 3-design; in particular, the set of stabilizer states forms a 3-design. Our work has profound implications for a number of research areas, such as quantum computation, quantum tomography, quantum foundation, and signal processing.

http://arxiv.org/abs/1504.03773
http://arxiv.org/abs/1510.02619

We present an efficient decoding algorithm for constant rate quantum hyper graph-product LDPC codes which provably corrects adversarial errors of weight proportional to the code minimum distance, or equivalently to the square-root of the block length. The algorithm runs in time linear in the number of qubits, which makes its performance the strongest to date for linear-time decoding of quantum codes. The algorithm relies on expanding properties, not of the quantum code's factor graph directly, but of the factor graph of the original classical code it is constructed from.

http://ieeexplore.ieee.org/xpl/articleDetails.jsp? arnumber=7354429
http://arxiv.org/abs/1504.00822

Many properties of quantum spin chains depend crucially on whether the Hamiltonian is gapped or gapless in the thermodynamic limit. Ground states of gapped Hamiltonians are weakly entangled, as quantified by the entanglement area law, and exhibit an exponential decay of correlation functions. For such systems the ground energy and the ground state itself can be efficiently computed using algorithms based on Matrix Product States. On the other hand, ground states of gapless spin chains can exhibit drastic violations of the area law, while computing the ground energy can be QMA-hard. Spin chain models studied in physics usually become gapless along quantum phase transition lines separating distinct gapped phases. Deciding whether a given family of Hamiltonians is gapped or gapless in the thermodynamic limit is therefore a fundamental problem. In this work we provide a complete solution of this problem for frustration-free translation invariant chains of qubits with nearest-neighbor interactions and open boundary conditions.

http://arxiv.org/abs/1503.04035

We propose a quantum algorithm for many-body state preparation. It is especially suited for injective PEPS and thermal states of local commuting Hamiltonians on a lattice. We show that for a uniform gap and sufficiently smooth paths, an adiabatic runtime and circuit depth of O(polylog(N)) can be achieved for O(N) spins. This is an almost exponential improvement over previous bounds. The total number of elementary gates scales as O(N polylog(N)). This is also faster than the best known upper bound of O(N^2) on the mixing times of Monte-Carlo Markov Chain algorithms for sampling classical systems in thermal equilibrium.

http://arxiv.org/abs/1508.00570