Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOptimal quantum algorithm for polynomial interpolation
84
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithms success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability. We end with a conjecture about the quantum query complexity of multivariate polynomial interpolation.
rate research
Read More
Function inversion is the problem that given a random function $f: [M] to [N]$, we want to find pre-image of any image $f^{-1}(y)$ in time $T$. In this work, we revisit this problem under the preprocessing model where we can compute some auxiliary information or advice of size $S$ that only depends on $f$ but not on $y$. It is a well-studied problem in the classical settings, however, it is not clear how quantum algorithms can solve this task any better besides invoking Grovers algorithm, which does not leverage the power of preprocessing. Nayebi et al. proved a lower bound $ST^2 ge tildeOmega(N)$ for quantum algorithms inverting permutations, however, they only consider algorithms with classical advice. Hhan et al. subsequently extended this lower bound to fully quantum algorithms for inverting permutations. In this work, we give the same asymptotic lower bound to fully quantum algorithms for inverting functions for fully quantum algorithms under the regime where $M = O(N)$. In order to prove these bounds, we generalize the notion of quantum random access code, originally introduced by Ambainis et al., to the setting where we are given a list of (not necessarily independent) random variables, and we wish to compress them into a variable-length encoding such that we can retrieve a random element just using the encoding with high probability. As our main technical contribution, we give a nearly tight lower bound (for a wide parameter range) for this generalized notion of quantum random access codes, which may be of independent interest.
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.
Quantum algorithm is an algorithm for solving mathematical problems using quantum systems encoded as information, which is found to outperform classical algorithms in some specific cases. The objective of this study is to develop a quantum algorithm for finding the roots of nth degree polynomials where n is any positive integer. In classical algorithm, the resources required for solving this problem increase drastically when n increases and it would be impossible to practically solve the problem when n is large. It was found that any polynomial can be rearranged into a corresponding companion matrix, whose eigenvalues are roots of the polynomial. This leads to a possibility to perform a quantum algorithm where the number of computational resources increase as a polynomial of n. In this study, we construct a quantum circuit representing the companion matrix and use eigenvalue estimation technique to find roots of polynomial.
We consider space-savi
We investigate the problem of synthesizing T-depth-optimal quantum circuits over the universal fault-tolerant Clifford+T gate set, where the implementation of the non-Clifford T-gate is the most expensive. We apply the nested-meet-in-the-middle(MITM) technique of Mosca,Mukhopadhyay(2020) and obtain a space-time trade-off to provably synthesize both depth and T-depth-optimal circuits. Specifically, using channel representation we design $Oleft(|mathbb{V}_n|^{leftlceilfrac{d}{c}rightrceil} right)$ time algorithm for T-depth-optimal circuits. $mathbb{V}_n$ is the set of some special T-depth-1 unitaries and $d$ is the minimum T-depth of input unitary. The MITM technique of Amy.et.al.(2013) has a complexity $left(left|mathcal{V}_nright|^{d/2}right)$, where $mathcal{V}_n$ is the set of T-depth-1 circuits. Since $|mathbb{V}_n| ll|mathcal{V}_{n}|$, our algorithm is much more efficient. For example, we take 2.152 seconds to generate $mathbb{V}_3$ (size 2282), Amy et al. takes about 4 days ($approx 3.5times 10^6$ seconds) to generate $mathcal{V}_{3}$ (size > 92,897,280). Inspired by the observations made by Mosca and Mukhopadhyay(2020), we design a $poly((log N)!,N,d)$ complexity heuristic algorithm for synthesizing T-depth-optimal circuits, where $N=2^n$. We synthesized previously unknown T-depth-optimal circuits for Fredkin, Peres, Negated-Toffoli and Quantum-XOR in $approx$ 27-28 minutes, and random 2 and 3-qubit unitaries with input T-depth in the range 2-20 and 2-7 respectively, and obtained output T-depth $leq$ input. There are no efficient T-depth-optimal synthesis algorithm to verify our results, but it is a good indication about the correctness of our claims for most unitaries.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
