Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum Implications of Huangs Sensitivity Theorem
113
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, the deterministic query complexity, $D(f)$, is at most quartic in the quantum query complexity, $Q(f)$: $D(f) = O(Q(f)^4)$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We also use the result to resolve the quantum analogue of the Aanderaa-Karp-Rosenberg conjecture. We show that if $f$ is a nontrivial monotone graph property of an $n$-vertex graph specified by its adjacency matrix, then $Q(f) = Omega(n)$, which is also optimal.
rate research
Read More
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, $bullet quad mathrm{deg}(f) = O(widetilde{mathrm{deg}}(f)^2)$: The degree of $f$ is at most quadratic in the approximate degree of $f$. This is optimal as witnessed by the OR function. $bullet quad mathrm{D}(f) = O(mathrm{Q}(f)^4)$: The deterministic query complexity of $f$ is at most quartic in the quantum query complexity of $f$. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). We apply these results to resolve the quantum analogue of the Aanderaa--Karp--Rosenberg conjecture. We show that if $f$ is a nontrivial monotone graph property of an $n$-vertex graph specified by its adjacency matrix, then $mathrm{Q}(f)=Omega(n)$, which is also optimal. We also show that the approximate degree of any read-once formula on $n$ variables is $Theta(sqrt{n})$.
In this note we give a version of Hao Huangs proof of the sensitivity conjecture, shedding some light on the origin of the magical matrix $A$ in that proof. For the history of the subject and the importance of this conjecture to the study of boolean functions, we refer to the original paper. Here we only state the main result: Consider the boolean cube $Q_n={0,1}^n$ as a graph, whose edges connect pairs of vertices differing in one coordinate. Then any its induced subgraph on greater than $2^{n-1}$ (the half) vertices has degree of some vertex at least $sqrt{n}$.
Valiant-Vazirani showed in 1985 [VV85] that solving NP with the promise that yes instances have only one witness is powerful enough to solve the entire NP class (under randomized reductions). We are interested in extending this result to the quantum setting. We prove extensions to the classes Merlin-Arthur MA and Quantum-Classical-Merlin-Arthur QCMA. Our results have implications for the complexity of approximating the ground state energy of a quantum local Hamiltonian with a unique ground state and an inverse polynomial spectral gap. We show that the estimation (to within polynomial accuracy) of the ground state energy of poly-gapped 1-D local Hamiltonians is QCMA-hard [AN02], under randomized reductions. This is in stark contrast to the case of constant gapped 1-D Hamiltonians, which is in NP [Has07]. Moreover, it shows that unless QCMA can be reduced to NP by randomized reductions, there is no classical description of the ground state of every poly-gapped local Hamiltonian that allows efficient calculation of expectation values. Finally, we discuss a few of the obstacles to the establishment of an analogous result to the class Quantum-Merlin-Arthur (QMA). In particular, we show that random projections fail to provide a polynomial gap between two witnesses.
We give a direct product theorem for the entanglement-assisted interactive quantum communication complexity of an $l$-player predicate $mathsf{V}$. In particular we show that for a distribution $p$ that is product across the input sets of the $l$ players, the success probability of any entanglement-assisted quantum communication protocol for computing $n$ copies of $mathsf{V}$, whose communication is $o(log(mathrm{eff}^*(mathsf{V},p))cdot n)$, goes down exponentially in $n$. Here $mathrm{eff}^*(mathsf{V}, p)$ is a distributional version of the quantum efficiency or partition bound introduced by Laplante, Lerays and Roland (2014), which is a lower bound on the distributional quantum communication complexity of computing a single copy of $mathsf{V}$ with respect to $p$. As an application of our result, we show that it is possible to do device-independent quantum key distribution (DIQKD) without the assumption that devices do not leak any information after inputs are provided to them. We analyze the DIQKD protocol given by Jain, Miller and Shi (2017), and show that when the protocol is carried out with devices that are compatible with $n$ copies of the Magic Square game, it is possible to extract $Omega(n)$ bits of key from it, even in the presence of $O(n)$ bits of leakage. Our security proof is parallel, i.e., the honest parties can enter all their inputs into their devices at once, and works for a leakage model that is arbitrarily interactive, i.e., the devices of the honest parties Alice and Bob can exchange information with each other and with the eavesdropper Eve in any number of rounds, as long as the total number of bits or qubits communicated is bounded.
The behavior of games repeated in parallel, when played with quantumly entangled players, has received much attention in recent years. Quantum analogues of Razs classical parallel repetition theorem have been proved for many special classes of games. However, for general entangled games no parallel repetition theorem was known. We prove that the entangled value of a two-player game $G$ repeated $n$ times in parallel is at most $c_G n^{-1/4} log n$ for a constant $c_G$ depending on $G$, provided that the entangled value of $G$ is less than 1. In particular, this gives the first proof that the entangled value of a parallel repeated game must converge to 0 for all games whose entangled value is less than 1. Central to our proof is a combination of both classical and quantum correlated sampling.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
