Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Optimized Quantum Maximum or Minimum Searching Algorithm and its Circuits
122
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Finding a maximum or minimum is a fundamental building block in many mathematical models. Compared with classical algorithms, Durr, Hoyers quantum algorithm (DHA) achieves quadratic speed. However, its key step, the quantum exponential searching algorithm (QESA), which is based on Grover algorithm, is not a sure-success algorithm. Meanwhile, quantum circuits encounter the gate decomposition problem due to variation of the scale of data. In this paper, we propose an optimized quantum algorithm for searching maximum and minimum, based on DHA and the optimal quantum exact search algorithm. Furthermore, we provide the corresponding quantum circuits, together with three equivalent simplifications. In circumstances when we can exactly estimate the ratio of the number of solutions M and the searched space N, our method can improve the successful probability close to 100%. Furthermore, compared with DHA, our algorithm shows an advantage in complexity with large databases and in the gate complexity of constructing oracles. Experiments have been executed on an IBM superconducting processor with two qubits, and a practical problem of finding the minimum from Titanic passengers age was numerically simulated. Both showed that our optimized maximum or minimum performs more efficiently compared with DHA. Our algorithm can serve as an important subroutine in various quantum algorithms which involves searching maximum or minimum.
rate research
Read More
We consider the long-time limit of out-of-time-order correlators (OTOCs) in two classes of quantum lattice models with time evolution governed by local unitary quantum circuits and maximal butterfly velocity $v_{B} = 1$. Using a transfer matrix approach, we present analytic results for the long-time value of the OTOC on and inside the light cone. First, we consider `dual-unitary circuits with various levels of ergodicity, including the integrable and non-integrable kicked Ising model, where we show exponential decay away from the light cone and relate both the decay rate and the long-time value to those of the correlation functions. Second, we consider a class of kicked XY models similar to the integrable kicked Ising model, again satisfying $v_{B}=1$, highlighting that maximal butterfly velocity is not exclusive to dual-unitary circuits.
Quantum communication relies on the existence of entanglement between two nodes of a network. Since, entanglement can only be produced using local quantum operations, distribution of parts of this entangled system between different nodes becomes necessary. However, due to the extremely fragile nature of entanglement and the presence of losses in the communication channel, the direct distribution of entanglement over large distances is nearly impossible. Quantum repeaters have been proposed to solve this problem. These enable one to establish long-range entanglement by dividing the link into smaller parts, creating entanglement between each part and connecting them up to form the full link. As researchers race to establish entanglement over larger and larger distances, it becomes essential to gauge the performance and robustness of the different protocols that go into designing a quantum repeater, before deploying them in real life. Present day noisy quantum computers are ideal for this task as they can emulate the noisy environment in a quantum communication channel and provide a benchmark for how the protocols will perform on real-life hardware. In this paper, we report the circuit-level implementation of the complete architecture of a Quantum Repeater. All the protocols of the repeater have been bench-marked on IBM Q, the worlds first publicly available cloud quantum computer. The results of our experiment provide a measure for the fidelity of entanglement current repeaters can establish. In addition, the repeater protocol provides a robust benchmark for the current state-of-the-art of quantum computing hardware.
We present a quantum algorithm for approximating maximum independent sets of a graph based on quantum non-Abelian adiabatic mixing in the sub-Hilbert space of degenerate ground states, which generates quantum annealing in a secondary Hamiltonian. For both sparse and dense graphs, our quantum algorithm on average can find an independent set of size very close to $alpha(G)$, which is the size of the maximum independent set of a given graph $G$. Numerical results indicate that an $O(n^2)$ time complexity quantum algorithm is sufficient for finding an independent set of size $(1-epsilon)alpha(G)$. The best classical approximation algorithm can produce in polynomial time an independent set of size about half of $alpha(G)$.
We present a detailed circuit implementation of Szegedys quantization of the Metropolis-Hastings walk. This quantum walk is usually defined with respect to an oracle. We find that a direct implementation of this oracle requires costly arithmetic operations and thus reformulate the quantum walk in a way that circumvents the implementation of that specific oracle and which closely follows the classical Metropolis-Hastings walk. We also present heuristic quantum algorithms that use the quantum walk in the context of discrete optimization problems and numerically study their performances. Our numerical results indicate polynomial quantum speedups in heuristic settings.
We show that low-depth random quantum circuits can be efficiently simulated by a quantum teleportation-inspired algorithm. By using logical qubits to redirect and teleport the quantum information in quantum circuits, the original circuits can be renormalized to new circuits with a smaller number of logical qubits. We demonstrate the algorithm to simulate several random quantum circuits, including 1D-chain 1000-qubit 42-depth, 2D-grid 125*8-qubit 42-depth and 2D-Bristlecone 72-qubit 32-depth circuits. Our results present a memory-efficient method with a clear physical picture to simulate low-depth random quantum circuits.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
