Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum computers can search rapidly by using almost any transformation
121
0
0.0
(
0
)
Authors
Lov K. Grover
Ask ChatGPT about the research
No Arabic abstract
A quantum computer has a clear advantage over a classical computer for exhaustive search. The quantum mechanical algorithm for exhaustive search was originally derived by using subtle properties of a particular quantum mechanical operation called the Walsh-Hadamard (W-H) transform. This paper shows that this algorithm can be implemented by replacing the W-H transform by almost any quantum mechanical operation. This leads to several new applications where it improves the number of steps by a square-root. It also broadens the scope for implementation since it demonstrates quantum mechanical algorithms that can readily adapt to available technology.
rate research
Read More
The first separation between quantum polynomial time and classical bounded-error polynomial time was due to Bernstein and Vazirani in 1993. They first showed a O(1) vs. Omega(n) quantum-classical oracle separation based on the quantum Hadamard transform, and then showed how to amplify this into a n^{O(1)} time quantum algorithm and a n^{Omega(log n)} classical query lower bound. We generalize both aspects of this speedup. We show that a wide class of unitary circuits (which we call dispersing circuits) can be used in place of Hadamards to obtain a O(1) vs. Omega(n) separation. The class of dispersing circuits includes all quantum Fourier transforms (including over nonabelian groups) as well as nearly all sufficiently long random circuits. Second, we give a general method for amplifying quantum-classical separations that allows us to achieve a n^{O(1)} vs. n^{Omega(log n)} separation from any dispersing circuit.
We consider the hypothesis that quantum mechanics is not fundamental, but instead emerges from a theory with less computational power, such as classical mechanics. This hypothesis makes the prediction that quantum computers will not be capable of sufficiently complex quantum computations. Utilizing this prediction, we outline a proposal to test for such a breakdown of quantum mechanics using near-term noisy intermediate-scale quantum (NISQ) computers. Our procedure involves simulating a non-Clifford random circuit, followed by its inverse, and then checking that the resulting state is the same as the initial state. We show that quantum mechanics predicts that the fidelity of this procedure decays exponentially with circuit depth (due to noise in NISQ computers). However, if quantum mechanics emerges from a theory with significantly less computational power, then we expect the fidelity to decay significantly more rapidly than the quantum mechanics prediction for sufficiently deep circuits, which is the experimental signature that we propose to search for. Useful experiments can be performed with 80 qubits and gate infidelity $10^{-3}$, while highly informative experiments should require only 1000 qubits and gate infidelity $10^{-5}$.
We study the explicit relation between violation of Bell inequalities and bipartite distillability of multi-qubit states. It has been shown that even though for $Nge 8$ there exist $N$-qubit bound entangled states which violates a Bell inequality [Phys. Rev. Lett. {bf 87}, 230402 (2001)], for all the states violating the inequality there exists at least one splitting of the parties into two groups such that pure-state entanglement can be distilled [Phys. Rev. Lett. {bf 88}, 027901 (2002)]. We here prove that for all $N$-qubit states violating the inequality the number of distillable bipartite splits increases exponentially with $N$, and hence the probability that a randomly chosen bipartite split is distillable approaches one exponentially with $N$, as $N$ tends to infinity. We also show that there exists at least one $N$-qubit bound entangled state violating the inequality if and only if $Nge 6$.
We introduce the multipartite collision model, defined in terms of elementary interactions between subsystems and ancillae, and show that it can simulate the Markovian dynamics of any multipartite open quantum system. We develop a method to estimate an analytical error bound for any repeated interactions model, and we use it to prove that the error of our scheme displays an optimal scaling. Finally, we provide a simple decomposition of the multipartite collision model into elementary quantum gates, and show that it is efficiently simulable on a quantum computer according to the dissipative quantum Church-Turing theorem, i.e. it requires a polynomial number of resources.
The goal of quantum circuit transformation is to map a logical circuit to a physical device by inserting additional gates as few as possible in an acceptable amount of time. We present an effective approach called TSA to construct the mapping. It consists of two key steps: one makes use of a combined subgraph isomorphism and completion to initialize some candidate mappings, the other dynamically modifies the mappings by using tabu search-based adjustment. Our experiments show that, compared with state-of-the-art methods GA, SABRE and FiDLS proposed in the literature, TSA can generate mappings with a smaller number of additional gates and it has a better scalability for large-scale circuits.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
