Search

Unitary equivariance is a natural symmetry that occurs in many contexts in physics and mathematics. Optimization problems with such symmetry can often be formulated as semidefinite programs for a d p + q -dimensional matrix variable that commutes with U ⊗ p ⊗ U ¯ ⊗ q , for all U ∈ U (d) . Solving such problems naively can be prohibitively expensive even if p + q is small but the local dimension d is large. We show that, under additional symmetry assumptions, this problem reduces to a linear program that can be solved in time that does not scale in d, and we provide a general framework to execute this reduction under different types of symmetries. The key ingredient of our method is a compact parametrization of the solution space by linear combinations of walled Brauer algebra diagrams. This parametrization requires the idempotents of a Gelfand–Tsetlin basis, which we obtain by adapting a general method inspired by the Okounkov–Vershik approach. To illustrate potential applications of our framework, we use several examples from quantum information: deciding the principal eigenvalue of a quantum state, quantum majority vote, asymmetric cloning and transformation of a black-box unitary. We also outline a possible route for extending our method to general unitary-equivariant semidefinite programs. [ABSTRACT FROM AUTHOR]

We prove that estimating the ground state energy of a translationally invariant, nearest-neighbour Hamiltonian on a 1D spin chain is $$\textsf {QMA}_{{\textsf {EXP}}}$$ -complete, even for systems of low local dimension ( $$\approx 40$$ ). This is an improvement over the best previously known result by several orders of magnitude, and it shows that spin-glass-like frustration can occur in translationally invariant quantum systems with a local dimension comparable to the smallest-known non-translationally invariant systems with similar behaviour. While previous constructions of such systems rely on standard models of quantum computation, we construct a new model that is particularly well-suited for encoding quantum computation into the ground state of a translationally invariant system. This allows us to shift the proof burden from optimizing the Hamiltonian encoding a standard computational model, to proving universality of a simple model. Previous techniques for encoding quantum computation into the ground state of a local Hamiltonian allow only a linear sequence of gates, hence only a linear (or nearly linear) path in the graph of all computational states. We extend these techniques by allowing significantly more general paths, including branching and cycles, thus enabling a highly efficient encoding of our computational model. However, this requires more sophisticated techniques for analysing the spectrum of the resulting Hamiltonian. To address this, we introduce a framework of graphs with unitary edge labels. After relating our Hamiltonian to the Laplacian of such a unitary labelled graph, we analyse its spectrum by combining matrix analysis and spectral graph theory techniques. [ABSTRACT FROM AUTHOR]

We solve an open problem by constructing quantum walks that not only detect but also find marked vertices in a graph. In the case when the marked set $$M$$ consists of a single vertex, the number of steps of the quantum walk is quadratically smaller than the classical hitting time $${{\mathrm{HT}}}(P,M)$$ of any reversible random walk $$P$$ on the graph. In the case of multiple marked elements, the number of steps is given in terms of a related quantity $${\hbox {HT}}^{+}(P,M)$$ which we call extended hitting time. Our approach is new, simpler and more general than previous ones. We introduce a notion of interpolation between the random walk $$P$$ and the absorbing walk $$P'$$ , whose marked states are absorbing. Then our quantum walk is simply the quantum analogue of this interpolation. Contrary to previous approaches, our results remain valid when the random walk $$P$$ is not state-transitive. We also provide algorithms in the cases when only approximations or bounds on parameters $$p_M$$ (the probability of picking a marked vertex from the stationary distribution) and $${\hbox {HT}}^{+}(P,M)$$ are known. [ABSTRACT FROM AUTHOR]

In this paper we study the subset of generalized quantum measurements on finite dimensional systems known as local operations and classical communication (LOCC). While LOCC emerges as the natural class of operations in many important quantum information tasks, its mathematical structure is complex and difficult to characterize. Here we provide a precise description of LOCC and related operational classes in terms of quantum instruments. Our formalism captures both finite round protocols as well as those that utilize an unbounded number of communication rounds. While the set of LOCC is not topologically closed, we show that finite round LOCC constitutes a compact subset of quantum operations. Additionally we show the existence of an open ball around the completely depolarizing map that consists entirely of LOCC implementable maps. Finally, we demonstrate a two-qubit map whose action can be approached arbitrarily close using LOCC, but nevertheless cannot be implemented perfectly. [ABSTRACT FROM AUTHOR]

We consider the class of protocols that can be implemented by local quantum operations and classical communication (LOCC) between two parties. In particular, we focus on the task of discriminating a known set of quantum states by LOCC. Building on the work in the paper Quantum nonlocality without entanglement (Bennett et al., Phys Rev A 59:1070-1091, ), we provide a framework for bounding the amount of nonlocality in a given set of bipartite quantum states in terms of a lower bound on the probability of error in any LOCC discrimination protocol. We apply our framework to an orthonormal product basis known as the domino states and obtain an alternative and simplified proof that quantifies its nonlocality. We generalize this result for similar bases in larger dimensions, as well as the 'rotated' domino states, resolving a long-standing open question (Bennett et al., Phys Rev A 59:1070-1091, ). [ABSTRACT FROM AUTHOR]

It is known that the number of different classical messages which can be communicated with a single use of a classical channel with zero probability of decoding error can sometimes be increased by using entanglement shared between sender and receiver. It has been an open question to determine whether entanglement can ever increase the zero-error communication rates achievable in the limit of many channel uses. In this paper we show, by explicit examples, that entanglement can indeed increase asymptotic zero-error capacity, even to the extent that it is equal to the normal capacity of the channel. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to enumerate the polynomial functions in n variables over a finite soluble group with chief factors of mutually coprime orders. For metabelian groups with chief factors of mutually coprime orders the term functions are also enumerated. The main technique employed is a decomposition of these groups of functions using the free differential calculus. [ABSTRACT FROM AUTHOR]

We investigate the sample complexity of Hamiltonian simulation: how many copies of an unknown quantum state are required to simulate a Hamiltonian encoded by the density matrix of that state? We show that the procedure proposed by Lloyd, Mohseni, and Rebentrost [Nat. Phys., 10(9):631–633, 2014] is optimal for this task. We further extend their method to the case of multiple input states, showing how to simulate any Hermitian polynomial of the states provided. As applications, we derive optimal algorithms for commutator simulation and orthogonality testing, and we give a protocol for creating a coherent superposition of pure states, when given sample access to those states. We also show that this sample-based Hamiltonian simulation can be used as the basis of a universal model of quantum computation that requires only partial swap operations and simple single-qubit states. Quantum Software from Quantum States: One of the hallmarks of quantum computation is the storage and extraction of information within quantum systems. Recently, Lloyd, Mohseni and Rebentrost created a protocol to treat multiple identical copies of a quantum state as "quantum software", specifying a quantum program to be run on any other state. They use this approach to do principal component analysis of the software state. Here, we expand on their results, providing protocols for running more-complex quantum programs specified by several different states. Our protocols can be used to analyze the relationship between different states (for example, deciding whether states are orthogonal) and to create new states (such as coherent linear combinations of two states). We also outline the optimality of Lloyd et al.'s original protocol, as well as our new protocols. [ABSTRACT FROM AUTHOR]