Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Basing One-way Permutations on NP-hard Problems under Quantum Reductions
221
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to average-case reductions. However, for many other classes such as NP, the evidence so far is typically negative, in the sense that the existence of such reductions would cause collapses of the polynomial hierarchy(PH). Basing cryptographic primitives, e.g., the average-case hardness of inverting one-way permutations, on NP-completeness is a particularly intriguing instance. As there is evidence showing that classical reductions from NP-hard problems to breaking these primitives result in PH collapses, it seems unlikely to base cryptographic primitives on NP-hard problems. Nevertheless, these results do not rule out the possibilities of the existence of quantum reductions. In this work, we initiate a study of the quantum analogues of these questions. Aside from formalizing basic notions of quantum reductions and demonstrating powers of quantum reductions by examples of separations, our main result shows that if NP-complete problems reduce to inverting one-way permutations using certain types of quantum reductions, then coNP $subseteq$ QIP(2).
rate research
Read More
The no-masking theorem says that masking quantum information is impossible in a bipartite scenario. However, there exist schemes to mask quantum states in multipartite systems. In this work, we show that, the joint measurement in the teleportation is really a masking process, when the apparatus is regarded as a quantum participant in the whole system.Based on the view, we present two four-partite maskers and a tripartite masker. One of the former provides a generalization in arbitrary dimension of the four-qubit scheme given by Li and Wang [Phys. Rev. A 98, 062306 (2018)], and the latter is precisely their tripartite scheme. The occupation probabilities and coherence of quantum states are masked in two steps of our schemes. And the information can be extracted naturally in their reverse processes.
The closest pair problem is a fundamental problem of computational geometry: given a set of $n$ points in a $d$-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in $O(nlog n)$ time in constant dimensions (i.e., when $d=O(1)$). This paper asks and answers the question of the problems quantum time complexity. Specifically, we give an $tilde{O}(n^{2/3})$ algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference. In $mathrm{polylog}(n)$ dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grovers algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the Quantum Strong Exponential Time Hypothesis (QSETH), which is based on the assumption that Grovers algorithm is optimal for CNF-SAT when the clause width is large. We show that the na{i}ve Grover approach to closest pair in higher dimensions is optimal up to an $n^{o(1)}$ factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.
203 -
Adrien Friggeri
, Eric Fleury (ENS / LIPn Laboratoire de lInformatique du Parallelisme / INRIA Grenoblen Rh^one-Alpes
2011
We show that the problem of finding a set with maximum cohesion in an undirected network is NP-hard.
One-way quantum computing is a promising candidate for fault-tolerant quantum computing. Here, we propose new protocols to realize a deterministic one-way CNOT gate and one-way $X$-rotations on quantum-computing platforms. By applying a delayed-choice scheme, we overcome a limit of most currently available quantum computers, which are unable to implement further operations on measured qubits or operations conditioned on measurement results from other qubits. Moreover, we decrease the error rate of the one-way logic gates, compared to the original protocol using local operations and classical communication (LOCC). In addition, we apply our deterministic one-way CNOT gate in the Deutsch-Jozsa algorithm to show the feasibility of our proposal. We demonstrate all these one-way gates and algorithms by running experiments on the cloud quantum-computing platform IBM Quantum Experience.
We propose a novel one-way quantum repeater architecture based on photonic tree-cluster states. Encoding a qubit in a photonic tree-cluster protects the information from transmission loss and enables long-range quantum communication through a chain of repeater stations. As opposed to conventional approaches that are limited by the two-way communication time, the overall transmission rate of the current quantum repeater protocol is determined by the local processing time enabling very high communication rates. We further show that such a repeater can be constructed with as little as two stationary qubits and one quantum emitter per repeater station, which significantly increases the experimental feasibility. We discuss potential implementations with diamond defect centers and semiconductor quantum dots efficiently coupled to photonic nanostructures and outline how such systems may be integrated into repeater stations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
