Automatic Generation of Grover Quantum Oracles for Arbitrary Data Structures

• URL: http://arxiv.org/abs/2110.07545v1
• Date: Thu, 14 Oct 2021 17:14:04 GMT
• Title: Automatic Generation of Grover Quantum Oracles for Arbitrary Data Structures
• Abstract summary: Grover's algorithm can be used for efficient search in unstructured databases. Quantum oracles that are frequently masked as black boxes play an important role in Grover's algorithm. We present a flexible method for automatically encoding unstructured databases into oracles, which can then be efficiently searched with Grover's algorithm.
• Score: 1.1091582432763736
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The steadily growing research interest in quantum computing - together with the accompanying technological advances in the realization of quantum hardware - fuels the development of meaningful real-world applications, as well as implementations for well-known quantum algorithms. One of the most prominent examples till today is Grover's algorithm, which can be used for efficient search in unstructured databases. Quantum oracles that are frequently masked as black boxes play an important role in Grover's algorithm. Hence, the automatic generation of oracles is of paramount importance. Moreover, the automatic generation of the corresponding circuits for a Grover quantum oracle is deeply linked to the synthesis of reversible quantum logic, which - despite numerous advances in the field - still remains a challenge till today in terms of synthesizing efficient and scalable circuits for complex boolean functions. In this paper, we present a flexible method for automatically encoding unstructured databases into oracles, which can then be efficiently searched with Grover's algorithm. Furthermore, we develop a tailor-made method for quantum logic synthesis, which vastly improves circuit complexity over other current approaches. Finally, we present another logic synthesis method that considers the requirements of scaling onto real world backends. We compare our method with other approaches through evaluating the oracle generation for random databases and analyzing the resulting circuit complexities using various metrics.

Related papers

• An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
  Quantum machine learning (QML) is a discipline that seeks to transfer the advantages of quantum computing to data-driven tasks. We propose an efficient approach that circumvents the costs associated with data encoding by mapping inputs to a finite set of Pauli strings. We evaluate our approach on text and image classification tasks, against well-established classical and quantum models.
  arXiv  Detail & Related papers  (2025-04-13T11:49:53Z)
• DeQompile: quantum circuit decompilation using genetic programming for explainable quantum architecture search [1.351147045576948]
  We introduce a novel genetic programming-based decompiler framework for reverse-engineering high-level quantum algorithms. The proposed approach is implemented in the open-source tool DeQompile.
  arXiv  Detail & Related papers  (2025-04-11T07:23:14Z)
• Automated Quantum Algorithm Synthesis [0.0]
  We present a method to automatically design the n-qubit realisations of quantum algorithms. We learn the algorithm structure rather than a specific unitary implementation. Our method proves robust, as it maintains performance across increasingly large search spaces.
  arXiv  Detail & Related papers  (2025-03-11T13:59:32Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum Circuit Synthesis and Compilation Optimization: Overview and Prospects [59.07692103357675]
  This survey explores the feasibility of an integrated design and optimization scheme that spans from the algorithmic level to quantum hardware.<n>It becomes more possible to reduce manual design costs, enhance the precision and efficiency of execution, and facilitate the implementation and validation of the superiority of quantum algorithms on hardware.
  arXiv  Detail & Related papers  (2024-06-30T15:50:10Z)
• Adaptive Circuit Learning of Born Machine: Towards Realization of Amplitude Embedding and Data Loading [7.88657961743755]
  We present a novel algorithm "Adaptive Circuit Learning of Born Machine" (ACLBM) Our algorithm is tailored to selectively integrate two-qubit entangled gates that best capture the complex entanglement present within the target state. Empirical results underscore the proficiency of our approach in encoding real-world data through amplitude embedding.
  arXiv  Detail & Related papers  (2023-11-29T16:47:31Z)
• Circuit complexity of quantum access models for encoding classical data [4.727325187683489]
  We study the Clifford$+T$ complexity of constructing some typical quantum access models. We show that both sparse-access input models and block-encoding require nearly linear circuit complexities. Our protocols are built upon improved quantum state preparation and a selective oracle for Pauli strings.
  arXiv  Detail & Related papers  (2023-11-19T16:23:57Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Analyses of the viability of automating the quantum circuit construction of Grover Oracle for executing wildcard searches on NISQ processors [0.0]
  This work investigates a technique for encoding search phrases used in wildcard searches. The suggested strategy will be useful for a range of wildcard search issues and could speed up the attainment of quantum advantage.
  arXiv  Detail & Related papers  (2023-03-14T05:33:09Z)
• The Basis of Design Tools for Quantum Computing: Arrays, Decision Diagrams, Tensor Networks, and ZX-Calculus [55.58528469973086]
  Quantum computers promise to efficiently solve important problems classical computers never will. A fully automated quantum software stack needs to be developed. This work provides a look "under the hood" of today's tools and showcases how these means are utilized in them, e.g., for simulation, compilation, and verification of quantum circuits.
  arXiv  Detail & Related papers  (2023-01-10T19:00:00Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Parametric Synthesis of Computational Circuits for Complex Quantum Algorithms [0.0]
  The purpose of our quantum synthesizer is enabling users to implement quantum algorithms using higher-level commands. The proposed approach for implementing quantum algorithms has a potential application in the field of machine learning.
  arXiv  Detail & Related papers  (2022-09-20T06:25:47Z)
• Hardware Efficient Quantum Search Algorithm [17.74233101199813]
  We propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. The circuit cost reduction leads to a remarkable improvement in the system success rates.
  arXiv  Detail & Related papers  (2021-03-26T01:08:50Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)
• 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)

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.