A Practical Quantum Algorithm for the Schur Transform

• URL: http://arxiv.org/abs/1709.07119v6
• Date: Wed, 21 Aug 2024 15:29:29 GMT
• Title: A Practical Quantum Algorithm for the Schur Transform
• Authors: William M. Kirby, Frederick W. Strauch,
• Abstract summary: We describe an efficient quantum algorithm for the quantum Schur transform. The Schur transform is an operation on a quantum computer that maps the standard computational basis to a basis composed of irreducible representations.
• Score: 0.09208007322096534
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We describe an efficient quantum algorithm for the quantum Schur transform. The Schur transform is an operation on a quantum computer that maps the standard computational basis to a basis composed of irreducible representations of the unitary and symmetric groups. We simplify and extend the algorithm of Bacon, Chuang, and Harrow, and provide a new practical construction as well as sharp theoretical and practical analyses. Our algorithm decomposes the Schur transform on $n$ qubits into $O\left(n^4\log\left(\frac{n}{\epsilon}\right)\right)$ operators in the Clifford+T fault-tolerant gate set and uses exactly $2\lfloor\log_2(n)\rfloor-1$ ancillary qubits. We extend our qubit algorithm to decompose the Schur transform on $n$ qudits of dimension $d$ into $O\left(n^{d^2+2}\log^p\left(\frac{n^{d^2+1}}{\epsilon}\right)\right)$ primitive operators from any universal gate set, for $p\approx3.97$.

Related papers

• Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
  This paper considers the problem for finding the $(,epsilon)$-Goldstein stationary point of Lipschitz continuous objective. We construct a zeroth-order quantum estimator for the surrogate oracle function.
  arXiv  Detail & Related papers  (2024-10-21T16:52:26Z)
• Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
  We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. We present a quantum algorithm that uses $O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$ queries to the block-encoding for any $Gamma$.
  arXiv  Detail & Related papers  (2024-04-04T17:58:01Z)
• Weak Schur sampling with logarithmic quantum memory [0.0]
  We introduce a new algorithm for the task of weak Schur sampling. Our algorithm efficiently determines both the Young label which indexes the irreducible representations and the multiplicity label of the symmetric group.
  arXiv  Detail & Related papers  (2023-09-21T10:02:46Z)
• Constant-depth circuits for Uniformly Controlled Gates and Boolean functions with application to quantum memory circuits [42.979881926959486]
  We propose two types of constant-depth constructions for implementing Uniformly Controlled Gates. We obtain constant-depth circuits for the quantum counterparts of read-only and read-write memory devices.
  arXiv  Detail & Related papers  (2023-08-16T17:54:56Z)
• Replicability in Reinforcement Learning [46.89386344741442]
  We focus on the fundamental setting of discounted MDPs with access to a generative model. Inspired by Impagliazzo et al. [2022], we say that an RL algorithm is replicable if, with high probability, it outputs the exact same policy after two executions.
  arXiv  Detail & Related papers  (2023-05-31T05:16:23Z)
• Gate Based Implementation of the Laplacian with BRGC Code for Universal Quantum Computers [0.0]
  We study the gate-based implementation of the binary reflected Gray code (BRGC) and binary code of the unitary time evolution operator due to the Laplacian discretized on a lattice with periodic boundary conditions. We present our algorithm for building the BRGC quantum circuit.
  arXiv  Detail & Related papers  (2022-07-24T03:15:25Z)
• Beyond Ans\"atze: Learning Quantum Circuits as Unitary Operators [30.5744362478158]
  We run gradient-based optimization in the Lie algebra $mathfrak u(2N)$. We argue that $U(2N)$ is not only more general than the search space induced by ansatz, but in ways easier to work with on classical computers.
  arXiv  Detail & Related papers  (2022-03-01T16:40:21Z)
• Quantum Algorithms for Ground-State Preparation and Green's Function Calculation [5.28670135448572]
  We present projective quantum algorithms for ground-state preparation and calculations of the many-body Green's functions in frequency domain. The algorithms are based on the linear combination of unitary (LCU) operations and essentially only use quantum resources.
  arXiv  Detail & Related papers  (2021-12-10T18:39:55Z)
• Primitive Quantum Gates for Dihedral Gauge Theories [0.0]
  We describe the simulation of dihedral gauge theories on digital quantum computers. The nonabelian discrete gauge group $D_N$ serves as an approximation to $U(1)timesbbZ$ lattice gauge theory.
  arXiv  Detail & Related papers  (2021-08-30T15:16:47Z)
• Quantum Instruction Set Design for Performance [30.049549820997996]
  A quantum instruction set is where quantum hardware and software meet. We develop new characterization and compilation techniques for non-Clifford gates to accurately evaluate different quantum instruction set designs.
  arXiv  Detail & Related papers  (2021-05-13T04:39:33Z)
• Quantum Legendre-Fenchel Transform [6.643082745560234]
  We present a quantum algorithm to compute the discrete Legendre-Fenchel transform. We show that our quantum algorithm is optimal up to polylogarithmic factors.
  arXiv  Detail & Related papers  (2020-06-08T18:00:05Z)

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.