Weak Schur sampling with logarithmic quantum memory
- URL: http://arxiv.org/abs/2309.11947v1
- Date: Thu, 21 Sep 2023 10:02:46 GMT
- Title: Weak Schur sampling with logarithmic quantum memory
- Authors: Enrique Cervero and Laura Man\v{c}inska
- Abstract summary: 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.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum Schur transform maps the computational basis of a system of $n$
qudits onto a \textit{Schur basis}, which spans the minimal invariant subspaces
of the representations of the unitary and the symmetric groups acting on the
state space of $n$ $d$-level systems. 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. There are two major advantages of our algorithm for
weak Schur sampling when compared to existing approaches which proceed via
quantum Schur transform algorithm or Generalized Phase Estimation algorithm.
First, our algorihtm is suitable for streaming applications and second it is
exponentially more efficient in its memory usage. We show that an instance of
our weak Schur sampling algorithm on $n$ qubits to accuracy $\epsilon$ requires
only $O(\log_2n)$ qubits of memory and $O(n^3\log_2(\frac{n}{\epsilon}))$ gates
from the Clifford+T set. Further, we show that our weak Schur sampling
algorithm on $n$ qudits decomposes into
$O\big(dn^{2d}\log_2^p\big(\frac{n^{2d}}{\epsilon}\big)\big)$ gates from an
arbitrary fault-tolerant qudit universal set, for $p\approx 4$, and requires a
memory of $O(\log_dn)$ qudits to implement.
Related papers
- Towards Optimal Circuit Size for Sparse Quantum State Preparation [10.386753939552872]
We consider the preparation for $n$-qubit sparse quantum states with $s$ non-zero amplitudes and propose two algorithms.
The first algorithm uses $O(ns/log n + n)$ gates, improving upon previous methods by $O(log n)$.
The second algorithm is tailored for binary strings that exhibit a short Hamiltonian path.
arXiv Detail & Related papers (2024-04-08T02:13:40Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
We present a scalable algorithm for the individually fair ($p$, $k$)-clustering problem introduced by Jung et al. and Mahabadi et al.
A clustering is then called individually fair if it has centers within distance $delta(x)$ of $x$ for each $xin P$.
We show empirically that not only is our algorithm much faster than prior work, but it also produces lower-cost solutions.
arXiv Detail & Related papers (2024-02-09T19:01:48Z) - Do you know what q-means? [50.045011844765185]
Clustering is one of the most important tools for analysis of large datasets.
We present an improved version of the "$q$-means" algorithm for clustering.
We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
arXiv Detail & Related papers (2023-08-18T17:52:12Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss.
Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z) - Quantum Simulation of the First-Quantized Pauli-Fierz Hamiltonian [0.5097809301149342]
We show that a na"ive partitioning and low-order splitting formula can yield, through our divide and conquer formalism, superior scaling to qubitization for large $Lambda$.
We also give new algorithmic and circuit level techniques for gate optimization including a new way of implementing a group of multi-controlled-X gates.
arXiv Detail & Related papers (2023-06-19T23:20:30Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model.
The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
arXiv Detail & Related papers (2022-08-11T04:12:50Z) - How to simulate quantum measurement without computing marginals [3.222802562733787]
We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis.
Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
arXiv Detail & Related papers (2021-12-15T21:44:05Z) - Streaming Complexity of SVMs [110.63976030971106]
We study the space complexity of solving the bias-regularized SVM problem in the streaming model.
We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
arXiv Detail & Related papers (2020-07-07T17:10:00Z) - A Practical Quantum Algorithm for the Schur Transform [0.09208007322096534]
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.
arXiv Detail & Related papers (2017-09-21T01:09:31Z)
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.