QIP · 2016

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.

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.

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.

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.

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}.

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.

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.

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.

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\%.

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.

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.

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.

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.

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.

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.

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 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.

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.

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.

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.

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 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.

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].

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 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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.