Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum proof systems for iterated exponential time, and beyond
149
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that any language in nondeterministic time $exp(exp(cdots exp(n)))$, where the number of iterated exponentials is an arbitrary function $R(n)$, can be decided by a multiprover interactive proof system with a classical polynomial-time verifier and a constant number of quantum entangled provers, with completeness $1$ and soundness $1 - exp(-Cexp(cdotsexp(n)))$, where the number of iterated exponentials is $R(n)-1$ and $C>0$ is a universal constant. The result was previously known for $R=1$ and $R=2$; we obtain it for any time-constructible function $R$. The result is based on a compression technique for interactive proof systems with entangled provers that significantly simplifies and strengthens a protocol compression result of Ji (STOC17). As a separate consequence of this technique we obtain a different proof of Slofstras recent result (unpublished) on the uncomputability of the entangled value of multiprover games. Finally, we show that even minor improvements to our compression result would yield remarkable consequences in computational complexity theory and the foundations of quantum mechanics: first, it would imply that the class MIP* contains all computable languages; second, it would provide a negative resolution to a multipartite version of Tsirelsons problem on the relation between the commuting operator and tensor product models for quantum correlations.
rate research
Read More
Quantum computers can sometimes exponentially outperform classical ones, but only for problems with sufficient structure. While it is well known that query problems with full permutation symmetry can have at most polynomial quantum speedup -- even for partial functions -- it is unclear how far this condition must be relaxed to enable exponential speedup. In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties, in which the input describes a graph and the output can only depend on its isomorphism class. We show that the answer to this question depends strongly on the input model. In the adjacency matrix model, we prove that the bounded-error randomized query complexity $R$ of any graph property $mathcal{P}$ has $R(mathcal{P}) = O(Q(mathcal{P})^{6})$, where $Q$ is the bounded-error quantum query complexity. This negatively resolves an open question of Montanaro and de Wolf in the adjacency matrix model. More generally, we prove $R(mathcal{P}) = O(Q(mathcal{P})^{3l})$ for any $l$-uniform hypergraph property $mathcal{P}$ in the adjacency matrix model. In direct contrast, in the adjacency list model for bounded-degree graphs, we exhibit a promise problem that shows an exponential separation between the randomized and quantum query complexities.
The expected return time to the original state is a key concept characterizing systems obeying both classical or quantum dynamics. We consider iterated open quantum dynamical systems in finite dimensional Hilbert spaces, a broad class of systems that includes classical Markov chains and unitary discrete time quantum walks on networks. Starting from a pure state, the time evolution is induced by repeated applications of a general quantum channel, in each timestep followed by a measurement to detect whether the system has returned to the original state. We prove that if the superoperator is unital in the relevant Hilbert space (the part of the Hilbert space explored by the system), then the expectation value of the return time is an integer, equal to the dimension of this relevant Hilbert space. We illustrate our results on partially coherent quantum walks on finite graphs. Our work connects the previously known quantization of the expected return time for bistochastic Markov chains and for unitary quantum walks, and shows that these are special cases of a more general statement. The expected return time is thus a quantitative measure of the size of the part of the Hilbert space available to the system when the dynamics is started from a certain state.
In this paper we study quantum algorithms for NP-complete problems whose best classical algorithm is an exponential time application of dynamic programming. We introduce the path in the hypercube problem that models many of these dynamic programming algorithms. In this problem we are asked whether there is a path from $0^n$ to $1^n$ in a given subgraph of the Boolean hypercube, where the edges are all directed from smaller to larger Hamming weight. We give a quantum algorithm that solves path in the hypercube in time $O^*(1.817^n)$. The technique combines Grovers search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems on graphs in the same time $O^*(1.817^n)$, and graph bandwidth in time $O^*(2.946^n)$. Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time $O^*(1.728^n)$.
Recently, Bravyi, Gosset, and K{o}nig (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). In other words, they exhibited a search problem in QNC^0 that is not in NC^0. We strengthen their result by proving that the 2D HLF problem is not contained in AC^0, the class of classical, polynomial-size, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates. We also supplement this worst-case lower bound with an average-case result: There exists a simple distribution under which any AC^0 circuit (even of nearly exponential size) has exponentially small correlation with the 2D HLF problem. Our results are shown by constructing a new problem in QNC^0, which we call the Relaxed Parity Halving Problem, which is easier to work with. We prove our AC^0 lower bounds for this problem, and then show that it reduces to the 2D HLF problem. As a step towards even stronger lower bounds, we present a search problem that we call the Parity Bending Problem, which is in QNC^0/qpoly (QNC^0 circuits that are allowed to start with a quantum state of their choice that is independent of the input), but is not even in AC^0[2] (the class AC^0 with unbounded fan-in XOR gates). All the quantum circuits in our paper are simple, and the main difficulty lies in proving the classical lower bounds. For this we employ a host of techniques, including a refinement of H{aa}stads switching lemmas for multi-output circuits that may be of independent interest, the Razborov-Smolensky AC^0[2] lower bound, Vaziranis XOR lemma, and lower bounds for non-local games.
In function inversion, we are given a function $f: [N] mapsto [N]$, and want to prepare some advice of size $S$, such that we can efficiently invert any image in time $T$. This is a well studied problem with profound connections to cryptography, data structures, communication complexity, and circuit lower bounds. Investigation of this problem in the quantum setting was initiated by Nayebi, Aaronson, Belovs, and Trevisan (2015), who proved a lower bound of $ST^2 = tildeOmega(N)$ for random permutations against classical advice, leaving open an intriguing possibility that Grovers search can be sped up to time $tilde O(sqrt{N/S})$. Recent works by Hhan, Xagawa, and Yamakawa (2019), and Chung, Liao, and Qian (2019) extended the argument for random functions and quantum advice, but the lower bound remains $ST^2 = tildeOmega(N)$. In this work, we prove that even with quantum advice, $ST + T^2 = tildeOmega(N)$ is required for an algorithm to invert random functions. This demonstrates that Grovers search is optimal for $S = tilde O(sqrt{N})$, ruling out any substantial speed-up for Grovers search even with quantum advice. Further improvements to our bounds would imply new classical circuit lower bounds, as shown by Corrigan-Gibbs and Kogan (2019). To prove this result, we develop a general framework for establishing quantum time-space lower bounds. We further demonstrate the power of our framework by proving quantum time-space lower bounds for Yaos box problem and salted cryptography.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
