Efficient Unitary T-designs from Random Sums

• URL: http://arxiv.org/abs/2402.09335v1
• Date: Wed, 14 Feb 2024 17:32:30 GMT
• Title: Efficient Unitary T-designs from Random Sums
• Authors: Chi-Fang Chen, Jordan Docter, Michelle Xu, Adam Bouland, Patrick Hayden
• Abstract summary: 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.
• Score: 0.6640968473398456
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Unitary $T$-designs play an important role in quantum information, with diverse applications in quantum algorithms, benchmarking, tomography, and communication. Until now, the most efficient construction of unitary $T$-designs for $n$-qudit systems has been via random local quantum circuits, which have been shown to converge to approximate $T$-designs in the diamond norm using $O(T^{5+o(1)} n^2)$ quantum gates. In this work, we provide a new construction of $T$-designs via random matrix theory using $\tilde{O}(T^2 n^2)$ quantum gates. Our construction leverages two key ideas. First, in the spirit of central limit theorems, we approximate the Gaussian Unitary Ensemble (GUE) by an i.i.d. sum of random Hermitian matrices. Second, we show that the product of just two exponentiated GUE matrices is already approximately Haar random. Thus, multiplying two exponentiated sums over rather simple random matrices yields a unitary $T$-design, via Hamiltonian simulation. A central feature of our proof is a new connection between the polynomial method in quantum query complexity and the large-dimension ($N$) expansion in random matrix theory. In particular, we show that the polynomial method provides exponentially improved bounds on the high moments of certain random matrix ensembles, without requiring intricate Weingarten calculations. In doing so, we define and solve a new type of moment problem on the unit circle, asking whether a finite number of equally weighted points, corresponding to eigenvalues of unitary matrices, can reproduce a given set of moments.

Related papers

• A Novel Finite Fractional Fourier Transform and its Quantum Circuit Implementation on Qudits [0.0]
  We present a new number theoretic definition of discrete fractional Fourier transform (DFrFT) The DFrFT is defined as the $N times N$ dimensional unitary representation of the generator of the arithmetic rotational group $SO_2[mathbbZ_pn]$.
  arXiv  Detail & Related papers  (2024-09-09T16:15:53Z)
• Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
  We show that products exponentiated sums of $S(N)$ permutations with random phases match the first $2Omega(n)$ moments of the Haar measure. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the method.
  arXiv  Detail & Related papers  (2024-04-25T17:08:34Z)
• 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)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• 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)
• Approximate orthogonality of permutation operators, with application to quantum information [0.9790236766474201]
  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.
  arXiv  Detail & Related papers  (2023-09-01T19:45:30Z)
• 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)
• On sampling determinantal and Pfaffian point processes on a quantum computer [49.1574468325115]
  DPPs were introduced by Macchi as a model in quantum optics the 1970s. Most applications require sampling from a DPP, and given their quantum origin, it is natural to wonder whether sampling a DPP on a classical computer is easier than on a classical one. Vanilla sampling consists in two steps, of respective costs $mathcalO(N3)$ and $mathcalO(Nr2)$ operations on a classical computer, where $r$ is the rank of the kernel matrix.
  arXiv  Detail & Related papers  (2023-05-25T08:43:11Z)
• On the moments of random quantum circuits and robust quantum complexity [0.0]
  We prove new lower bounds on the growth of robust quantum circuit complexity. We show two bounds for random quantum circuits with local gates drawn from a subgroup of $SU(4)$.
  arXiv  Detail & Related papers  (2023-03-29T18:06:03Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• 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)

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.