Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNP problem in quantum algorithm
74
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In complexity theory, there exists a famous unsolved problem whether NP can be P or not. In this paper, we discuss this aspect in SAT (satisfiability) problem, and it is shown that the SAT can be solved in plynomial time by means of quantum algorithm.
rate research
Read More
We present a quasipolynomial-time algorithm for solving the weak membership problem for the convex set of separable, i.e. non-entangled, bipartite density matrices. The algorithm decides whether a density matrix is separable or whether it is eps-away from the set of the separable states in time exp(O(eps^-2 log |A| log |B|)), where |A| and |B| are the local dimensions, and the distance is measured with either the Euclidean norm, or with the so-called LOCC norm. The latter is an operationally motivated norm giving the optimal probability of distinguishing two bipartite quantum states, each shared by two parties, using any protocol formed by quantum local operations and classical communication (LOCC) between the parties. We also obtain improved algorithms for optimizing over the set of separable states and for computing the ground-state energy of mean-field Hamiltonians. The techniques we develop are also applied to quantum Merlin-Arthur games, where we show that multiple provers are not more powerful than a single prover when the verifier is restricted to LOCC protocols, or when the verification procedure is formed by a measurement of small Euclidean norm. This answers a question posed by Aaronson et al (Theory of Computing 5, 1, 2009) and provides two new characterizations of the complexity class QMA, a quantum analog of NP. Our algorithm uses semidefinite programming to search for a symmetric extension, as first proposed by Doherty, Parrilo and Spedialieri (Phys. Rev. A, 69, 022308, 2004). The bound on the runtime follows from an improved de Finetti-type bound quantifying the monogamy of quantum entanglement, proved in (arXiv:1010.1750). This result, in turn, follows from a new lower bound on the quantum conditional mutual information and the entanglement measure squashed entanglement.
Entanglement detection in high dimensional systems is a NP-hard problem since it is lacking an efficient way. Given a bipartite quantum state of interest free entanglement can be detected efficiently by the PPT-criterion (Peres-Horodecki criterion), in contrast to detecting bound entanglement, i.e. a curious form of entanglement that can also not be distilled into maximally (free) entangled states. Only a few bound entangled states have been found, typically by constructing dedicated entanglement witnesses, so naturally the question arises how large is the volume of those states. We define a large family of magically symmetric states of bipartite qutrits for which we find $82%$ to be free entangled, $2%$ to be certainly separable and as much as $10%$ to be bound entangled, which shows that this kind of entanglement is not rare. Via various machine learning algorithms we can confirm that the remaining $6%$ of states are more likely to belonging to the set of separable states than bound entangled states. Most important we find via dimension reduction algorithms that there is a strong $2$-dimensional (linear) sub-structure in the set of bound entangled states. This revealed structure opens a novel path to find and characterize bound entanglement towards solving the long-standing problem of what the existence of bound entanglement is implying.
We study a delay-sensitive information flow problem where a source streams information to a sink over a directed graph G(V,E) at a fixed rate R possibly using multiple paths to minimize the maximum end-to-end delay, denoted as the Min-Max-Delay problem. Transmission over an edge incurs a constant delay within the capacity. We prove that Min-Max-Delay is weakly NP-complete, and demonstrate that it becomes strongly NP-complete if we require integer flow solution. We propose an optimal pseudo-polynomial time algorithm for Min-Max-Delay, with time complexity O(log (Nd_{max}) (N^5d_{max}^{2.5})(log R+N^2d_{max}log(N^2d_{max}))), where N = max{|V|,|E|} and d_{max} is the maximum edge delay. Besides, we show that the integrality gap, which is defined as the ratio of the maximum delay of an optimal integer flow to the maximum delay of an optimal fractional flow, could be arbitrarily large.
The Systematic Normal Form (SysNF) is a canonical form of lattices introduced in [Eldar,Shor 16], in which the basis entries satisfy a certain co-primality condition. Using a smooth analysis of lattices by SysNF lattices we design a quantum algorithm that can efficiently solve the following variant of the bounded-distance-decoding problem: given a lattice L, a vector v, and numbers b = {lambda}_1(L)/n^{17}, a = {lambda}_1(L)/n^{13} decide if vs distance from L is in the range [a/2, a] or at most b, where {lambda}_1(L) is the length of Ls shortest non-zero vector. Improving these parameters to a = b = {lambda}_1(L)/sqrt{n} would invalidate one of the security assumptions of the Learning-with-Errors (LWE) cryptosystem against quantum attacks.
A boundary evolution Algorithm (BEA) is proposed by simultaneously taking into account the bottom and the high-level crossover and mutation, ie., the boundary of the hierarchical genetic algorithm. Operators and optimal individuals based on optional annealing are designed. Based on the numerou
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
