Related papers: Testing and Learning Quantum Juntas Nearly Optimally

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)
Quantum Algorithm for Online Exp-concave Optimization [30.962392035110135]
We present quantum online quasi-Newton methods to tackle the problem. Our method approximates the Hessian by quantum estimated inexact gradient. Such regret improves the optimal classical algorithm by a factor of $T2/3$.
arXiv Detail & Related papers (2024-10-25T16:58:44Z)
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.