Two of the key properties of quantum physics are the no-signaling principle and the Grover search lower bound. That is, despite admitting stronger-than-classical correlations, quantum mechanics does not imply superluminal signaling, and despite a form of exponential parallelism, quantum mechanics does not imply polynomial-time brute force solution of NP-complete problems. Here, we investigate the degree to which these two properties are connected. We examine four classes of deviations from quantum mechanics, for which we draw inspiration from the literature on the black hole information paradox. We show that in these models, the physical resources required to send a superluminal signal scale polynomially with the resources needed to speed up Grover's algorithm. Hence the no-signaling principle is equivalent to the inability to solve NP-hard problems efficiently by brute force within the classes of theories analyzed.
Two of the key properties of quantum physics are the no-signaling principle and the Grover search lower bound. That is, despite admitting stronger-than-classical correlations, quantum mechanics does not imply superluminal signaling, and despite a form of exponential parallelism, quantum mechanics does not imply polynomial-time brute force solution of NP-complete problems. Here, we investigate the degree to which these two properties are connected. We examine four classes of deviations from quantum mechanics, for which we draw inspiration from the literature on the black hole information paradox. We show that in these models, the physical resources required to send a superluminal signal scale polynomially with the resources needed to speed up Grover's algorithm. Hence the no-signaling principle is equivalent to the inability to solve NP-hard problems efficiently by brute force within the classes of theories analyzed.
Grover's algorithm constitutes the optimal quantum solution to the search problem and provides a quadratic speed-up over all possible classical search algorithms. Quantum interference between computational paths has been posited as a key resource behind this computational speed-up. However there is a limit to this interference, at most pairs of paths can ever interact in a fundamental way. Could more interference imply more computational power? Sorkin has defined a hierarchy of possible interference behaviours—currently under experimental investigation—where classical theory is at the first level of the hierarchy and quantum theory belongs to the second. Informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In this work, we consider how Grover's speed-up depends on the order of interference in a theory. Surprisingly, we show that the quadratic lower bound holds regardless of the order of interference. Thus, at least from the point of view of the search problem, post-quantum interference does not imply a computational speed-up over quantum theory.
The quantum foundations literature contains dozens of "no-signaling" arguments that rely on the Born rule or, more generally, the positive operator-valued measure (POVM) framework to show that the resources of non-relativistic quantum mechanics (NRQM) cannot be used to send superluminal signals. What these arguments typically establish, however, is not a prohibition on superluminal signaling per se, but the seemingly stronger claim that signaling at any speed between mutually isolated systems is forbidden. This paper gives a precise formulation of this claim, the no-signaling hypothesis, and investigates the following converse question: under what additional assumptions does it imply that all experimental outcome probabilities are described by POVMs? Surprisingly few are needed: given the standard NRQM representation of composite experiments and two textbook claims about marginal probabilities, the no-signaling hypothesis is equivalent to the universality of the POVM framework. More broadly, by formalizing the relevant concepts and deriving the logical relationships between them, the paper shows that the no-signaling hypothesis can be used to derive most, though not all, of the probability-generating fragment of NRQM. The resulting map of implications clarifies which common postulates of NRQM are logically interrelated and which can be modified independently.
Grover's algorithm can solve NP-complete problems on quantum computers faster than all the known algorithms on classical computers. However, Grover's algorithm still needs exponential time. Due to the BBBV theorem, Grover's algorithm is optimal for searches in the domain of a function, when the function is used as a black box. We analyze the NP-complete set {(⟨M⟩,1n,1t)∣ TM M accepts an x∈{0,1}n within t steps}. If t is large enough, then M accepts each word in L(M) with length n within t steps. So, one can use methods from computability theory to show that black box searching is the fastest way to find a solution. Therefore, Grover's algorithm is optimal for NP-complete problems.
In this chapter, we introduce the domain of quantum information. Quantum physics is much more than a perspective for new supports of information taking advantage of nanotechnologies. In fact, the quantum physics enables state superposition which can lead to significant breakthrough in computer programming. For example, the Grover algorithm brings the cost of partial search below complexity n instead of average complexity n /2 with classic computer, where n is the dataset size. Basically, the algorithm performs an inverse function computation when the direct function is given by a black box (i.e. has no particular structural property). The use of Grover algorithm could greatly impair the protection of transactions with cryptocurrencies if the quantum computers were to be generalized. Shore algorithm based on quantum Fourier transform in theory performs the factorization of numbers in O ( n 2 ), where n is the size of the number to be factorized. There is no known polynomial algorithm on classic computers to perform this task. However, the problem is not supposed to be NP hard. Indeed, it is believed that quantum computing cannot make NP-hard problems polynomial. We also look to one of the most spectacular quantum effects which is called the intrication . It allows a pair of particularly conditioned particles to be connected regardless of time and space. The intricacy was instrumental to prove via Bell inequality that the quantum measurement is indeed purely not deterministic. Although the connection between intricated particles is not expected to carry information in apparent faster than light transfer, however it leads to science fiction application such as teleportation, already experimented on system of few individual particles.
Can Grover's quantum search algorithm speed up search of a physical region - for example a 2D grid of size /spl radic/n x /spl radic/n? The problem is that /spl radic/n time seems to be needed for each query, just to move amplitude across the grid. Here we show that this problem can be surmounted, refuting a claim to the contrary by Benioff. In particular, we show how to search a d-dimensional hypercube in time 0(/spl radic/n) for d /spl ges/ 3, or 0(/spl radic/n log/sup 3/ n) for d = 2. More generally, we introduce a model of quantum query complexity on graphs, motivated by fundamental physical limits on information storage, particularly the holographic principle from black hole thermodynamics. Our results in this model include almost-tight upper and lower bounds for many search tasks; a generalized algorithm that works for any graph with good expansion properties, not just hypercubes; and relationships among several notions of locality for unitary matrices acting on graphs. As an application of our results, we give an 0(/spl radic/n)-qubit communication protocol for the disjointness problem, which improves an upper bound of Hoyer and de Wolf and matches a lower bound of Razborov.
We consider the problem of deriving the no-signaling condition from the assumption that, as seen from a complexity theoretic perspective, the universe is not an exponential place. A fact that disallows such a derivation is the existence of polynomial superluminal gates, hypothetical primitive operations that enable superluminal signaling but not the efficient solution of intractable problems. It therefore follows, if this assumption is a basic principle of physics, either that it must be supplemented with additional assumptions to prohibit such gates or, improbably, that no-signaling is not a universal condition. Yet a gate of this kind is possibly implicit, although not recognized as such, in a decade-old quantum optical experiment involving position–momentum entangled photons. Here, we describe a feasible modified version of the experiment that appears to explicitly demonstrate the action of this gate. Some obvious counter-claims are shown to be invalid. We believe that the unexpected possibility of polynomial superluminal operations arises because some practically measured quantum optical quantities are not describable as standard quantum mechanical observables.