Approximate orthogonality of permutation operators, with application to quantum information

• URL: http://arxiv.org/abs/2309.00715v1
• Date: Fri, 1 Sep 2023 19:45:30 GMT
• Title: Approximate orthogonality of permutation operators, with application to quantum information
• Authors: Aram W. Harrow
• Abstract summary: Consider the $n!$ different unitary matrices that permute $n$ $d$-dimensional quantum systems. If $dgeq n$ then they are linearly independent. This simple point has several applications in quantum information and random matrix theory.
• Score: 0.9790236766474201
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Consider the $n!$ different unitary matrices that permute $n$ $d$-dimensional quantum systems. If $d\geq n$ then they are linearly independent. This paper discusses a sense in which they are approximately orthogonal (with respect to the Hilbert-Schmidt inner product) if $d\gg n^2$, or, in a different sense, if $d\gg n$. Previous work had shown pairwise approximate orthogonality of these matrices, but here we show a more collective statement, quantified in terms of the operator norm distance of the Gram matrix to the identity matrix. This simple point has several applications in quantum information and random matrix theory: (1) showing that random maximally entangled states resemble fully random states, (2) showing that Boson sampling output probabilities resemble those from Gaussian matrices, (3) improving the Eggeling-Werner scheme for multipartite data hiding, (4) proving that the product test of Harrow-Montanaro cannot be performed using LOCC without a large number of copies of the state to be tested, (5) proving that the purity of a quantum state also cannot be efficiently tested using LOCC, and (6, published separately) helping prove that poly-size random quantum circuits are poly-designs.

Related papers

• Efficient conversion from fermionic Gaussian states to matrix product states [48.225436651971805]
  We propose a highly efficient algorithm that converts fermionic Gaussian states to matrix product states. It can be formulated for finite-size systems without translation invariance, but becomes particularly appealing when applied to infinite systems. The potential of our method is demonstrated by numerical calculations in two chiral spin liquids.
  arXiv  Detail & Related papers  (2024-08-02T10:15:26Z)
• Efficient Unitary T-designs from Random Sums [0.6640968473398456]
  Unitary $T$-designs play an important role in quantum information, with diverse applications in quantum algorithms, benchmarking, tomography, and communication. We provide a new construction of $T$-designs via random matrix theory using $tildeO(T2 n2)$ quantum gates.
  arXiv  Detail & Related papers  (2024-02-14T17:32:30Z)
• Polynomial-depth quantum algorithm for computing matrix determinant [46.13392585104221]
  We propose an algorithm for calculating the determinant of a square matrix, and construct a quantum circuit realizing it. Each row of the matrix is encoded as a pure state of some quantum system. The admitted matrix is therefore arbitrary up to the normalization of quantum states of those systems.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• Quantum Time-Space Tradeoffs for Matrix Problems [0.5524804393257919]
  We consider the time and space required for quantum computers to solve a range of problems involving matrices. For almost all matrices $A$, we prove that quantum circuits with at most $T$ input queries and $S$ qubits of memory require $T=Omega(n2/S)$. Because many of our lower bounds match deterministic algorithms with the same time and space complexity, we show that quantum computers cannot provide any advantage for these problems with any space bound.
  arXiv  Detail & Related papers  (2024-01-10T18:38:43Z)
• Vectorization of the density matrix and quantum simulation of the von Neumann equation of time-dependent Hamiltonians [65.268245109828]
  We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations. We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix. A quantum algorithm to simulate the dynamics of the density matrix is proposed.
  arXiv  Detail & Related papers  (2023-06-14T23:08:51Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  We show that learning $ktimes k$, rank-$r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ samples. We propose an algorithm that uses $cal O(frackrepsilon2log2fracepsilon)$ samples, a number linear in the high dimension, and nearly linear in the matrices, typically low, rank proofs.
  arXiv  Detail & Related papers  (2020-09-30T19:10:32Z)
• Mapping quantum random walks onto a Markov chain by mapping a unitary transformation to a higher dimension of an irreducible matrix [0.0]
  A new process, discrete in time and space, yields the results of both a random walk and a quantum random walk. Results for a quantum random walk on infinite and finite lines are introduced.
  arXiv  Detail & Related papers  (2020-06-19T11:50:07Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.