Near-perfect Reachability of Variational Quantum Search with Depth-1 Ansatz

• URL: http://arxiv.org/abs/2301.13224v1
• Date: Mon, 30 Jan 2023 19:00:07 GMT
• Title: Near-perfect Reachability of Variational Quantum Search with Depth-1 Ansatz
• Authors: Junpeng Zhan
• Abstract summary: Grover's search algorithm is renowned for its dramatic speedup in solving scientific problems. The recently proposed Variational Quantum Search (VQS) algorithm has shown an exponential advantage over Grover's algorithm for up to 26 qubits. Here we show that the exponentially deep circuit required by Grover's algorithm can be replaced by a multi-controlled NOT gate.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Grover's search algorithm is renowned for its dramatic speedup in solving many important scientific problems. The recently proposed Variational Quantum Search (VQS) algorithm has shown an exponential advantage over Grover's algorithm for up to 26 qubits. However, its advantage for larger numbers of qubits has not yet been proven. Here we show that the exponentially deep circuit required by Grover's algorithm can be replaced by a multi-controlled NOT gate together with either a single layer of Ry gates or two layers of circuits consisting of Hadamard and NOT gates, which is valid for any number of qubits greater than five. We prove that the VQS, with a single layer of Ry gates as its Ansatz, has near-perfect reachability in finding the good element of an arbitrarily large unstructured data set, and its reachability exponentially improves with the number of qubits, where the reachability is defined to quantify the ability of a given Ansatz to generate an optimal quantum state. Numerical studies further validate the excellent reachability of the VQS. Proving the near-perfect reachability of the VQS, with a depth-1 Ansatz, for any number of qubits completes an essential step in proving its exponential advantage over Grover's algorithm for any number of qubits, and the latter proving is significant as it means that the VQS can efficiently solve NP-complete problems.

Related papers

• Distributed Exact Generalized Grover's Algorithm [9.675088142486729]
  We propose a distributed Exactized Grover's Algorithm (DEGGA) to solve a generalized search problem. Our algorithm ensures accuracy, with a theoretical probability of identifying the target states at $100%$. Our method requires a total of $n$ qubits, eliminating the need for auxiliary qubits.
  arXiv  Detail & Related papers  (2024-05-11T09:17:11Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Utilizing Novel Quantum Counters for Grover's Algorithm to Solve the Dominating Set Problem [0.0]
  Grover's algorithm is a well-known unstructured quantum search algorithm run on quantum computers. This paper utilizes novel quantum counters with three good properties to construct the oracle of Grover's algorithm.
  arXiv  Detail & Related papers  (2023-12-14T23:00:35Z)
• Variational Quantum Search with Shallow Depth for Unstructured Database Search [0.0]
  Variational Quantum Search (VQS) is a novel algorithm based on variational quantum algorithms and parameterized quantum circuits. We show that a depth-10 Ansatz can amplify the total probability of $k$ out of $2n$ elements represented by $n$+1 qubits. We demonstrate that a depth-56 circuit in VQS can replace a depth-270,989 circuit in Grover's algorithm.
  arXiv  Detail & Related papers  (2022-12-16T17:16:54Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Quantum Speedup for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection [2.5272389610447856]
  We propose a quantum algorithm that supports a real-valued higher-order unconstrained binary optimization problem. The proposed algorithm is capable of reducing the query complexity in the classical domain and providing a quadratic speedup in the quantum domain.
  arXiv  Detail & Related papers  (2022-05-31T00:14:49Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Efficiently Solve the Max-cut Problem via a Quantum Qubit Rotation Algorithm [7.581898299650999]
  We introduce a simple yet efficient algorithm named Quantum Qubit Rotation Algorithm (QQRA) The approximate solution of the max-cut problem can be obtained with probability close to 1. We compare it with the well known quantum approximate optimization algorithm and the classical Goemans-Williamson algorithm.
  arXiv  Detail & Related papers  (2021-10-15T11:19:48Z)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.