Testing and Learning Quantum Juntas Nearly Optimally
- URL: http://arxiv.org/abs/2207.05898v3
- Date: Fri, 27 Oct 2023 06:36:13 GMT
- Title: Testing and Learning Quantum Juntas Nearly Optimally
- Authors: Thomas Chen, Shivam Nadimpalli, Henry Yuen
- Abstract summary: We consider the problem of testing and learning quantum $k$-juntas.
We give (a) a $widetildeO(sqrtk)$-query quantum algorithm that can distinguish quantum $k$-juntas from unitary matrices that are "far" from every quantum $k$-junta.
We complement our upper bounds for testing quantum $k$-juntas and learning quantum $k$-juntas with near-matching lower bounds of $Omega(sqrtk)$ and $Omega(frac
- Score: 3.030969076856776
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of testing and learning quantum $k$-juntas: $n$-qubit
unitary matrices which act non-trivially on just $k$ of the $n$ qubits and as
the identity on the rest. As our main algorithmic results, we give (a) a
$\widetilde{O}(\sqrt{k})$-query quantum algorithm that can distinguish quantum
$k$-juntas from unitary matrices that are "far" from every quantum $k$-junta;
and (b) a $O(4^k)$-query algorithm to learn quantum $k$-juntas. We complement
our upper bounds for testing quantum $k$-juntas and learning quantum $k$-juntas
with near-matching lower bounds of $\Omega(\sqrt{k})$ and
$\Omega(\frac{4^k}{k})$, respectively. Our techniques are Fourier-analytic and
make use of a notion of influence of qubits on unitaries.
Related papers
- Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
We present a quantum generalization of these tools through a generic bottleneck lemma.
This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles.
Even with sublinear barriers, we use Feynman-Kac techniques to lift classical to quantum ones establishing tight lower bound $T_mathrmmix = 2Omega(nalpha)$.
arXiv Detail & Related papers (2024-11-06T22:51:27Z) - 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) - Fast Quantum Algorithms for Trace Distance Estimation [8.646488471216262]
We propose efficient quantum algorithms for estimating the trace distance within additive error $varepsilon$ between mixed quantum states of rank $r$.
We show that the decision version of low-rank trace distance estimation is $mathsfBQP$-complete.
arXiv Detail & Related papers (2023-01-17T10:16:14Z) - The Quantum and Classical Streaming Complexity of Quantum and Classical
Max-Cut [0.07614628596146598]
We investigate the space complexity of two graph streaming problems: Max-Cut and its quantum analogue, Quantum Max-Cut.
Our work resolves the quantum and classical approximability of quantum and classical Max-Cut using $textrmo(n)$ space.
arXiv Detail & Related papers (2022-06-01T03:40:56Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Exponential separations between learning with and without quantum memory [17.763817187554096]
We study the power of quantum memory for learning properties of quantum systems and dynamics.
Many state-of-the-art learning algorithms require access to an additional external quantum memory.
We show that this trade-off is inherent in a wide range of learning problems.
arXiv Detail & Related papers (2021-11-10T19:03:49Z) - Sample Complexity of Learning Quantum Circuits [4.329298109272386]
We prove that physical quantum circuits are PAC learnable on a quantum computer via empirical risk minimization.
Our results provide a valuable guide for quantum machine learning in both theory and experiment.
arXiv Detail & Related papers (2021-07-19T18:00:04Z) - Quantum Algorithm for Fidelity Estimation [8.270684567157987]
For two unknown mixed quantum states $rho$ and $sigma$ in an $N$-dimensional space, computing their fidelity $F(rho,sigma)$ is a basic problem.
We propose a quantum algorithm that solves this problem in $namepoly(log (N), r, 1/varepsilon)$ time.
arXiv Detail & Related papers (2021-03-16T13:57:01Z) - 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) - Quantum Coupon Collector [62.58209964224025]
We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements.
We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
arXiv Detail & Related papers (2020-02-18T16:14:55Z)
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.