A quantum algorithm to estimate the closeness to the Strict Avalanche criterion in Boolean functions

• URL: http://arxiv.org/abs/2211.15356v1
• Date: Fri, 25 Nov 2022 12:32:01 GMT
• Title: A quantum algorithm to estimate the closeness to the Strict Avalanche criterion in Boolean functions
• Authors: C. A. Jothishwaran, Abhishek Chakraborty, Vishvendra Singh Poonia, Pantelimon Stanica, Sugata Gangopadhyay
• Abstract summary: We propose a quantum algorithm that estimates the closeness of a given Boolean function to one that satisfies the strict avalanche criterion'' (SAC) This algorithm requires $n$ queries of the Boolean function oracle, where $n$ is the number of input variables. It is shown our algorithm verifies SAC with the fewest possible calls to quantum oracle and requires the fewest samples for a given confidence bound.
• Score: 4.392337343771302
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose a quantum algorithm (in the form of a quantum oracle) that estimates the closeness of a given Boolean function to one that satisfies the ``strict avalanche criterion'' (SAC). This algorithm requires $n$ queries of the Boolean function oracle, where $n$ is the number of input variables, this is fewer than the queries required by the classical algorithm to perform the same task. We compare our approach with other quantum algorithms that may be used for estimating the closeness to SAC and it is shown our algorithm verifies SAC with the fewest possible calls to quantum oracle and requires the fewest samples for a given confidence bound.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Efficient Implementation of a Quantum Search Algorithm for Arbitrary N [0.0]
  This paper presents an enhancement to Grover's search algorithm for instances where $N$ is not a power of 2. By employing an efficient algorithm for the preparation of uniform quantum superposition states over a subset of the computational basis states, we demonstrate that a considerable reduction in the number of oracle calls (and Grover's iterations) can be achieved in many cases.
  arXiv  Detail & Related papers  (2024-06-19T19:16:40Z)
• When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
  We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input. For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer. For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
  arXiv  Detail & Related papers  (2023-12-18T18:29:01Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios. We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
  arXiv  Detail & Related papers  (2023-06-15T15:28:12Z)
• Quantum Search Approaches to Sampling-Based Motion Planning [0.0]
  We present a novel formulation of traditional sampling-based motion planners as database-oracle structures that can be solved via quantum search algorithms. We consider two complementary scenarios: for simpler sparse environments, we formulate the Quantum Full Path Search Algorithm (q-FPS), which creates a superposition of full random path solutions. For dense unstructured environments, we formulate the Quantum Rapidly Exploring Random Tree algorithm, q-RRT, that creates quantum superpositions of possible parent-child connections.
  arXiv  Detail & Related papers  (2023-04-10T19:12:25Z)
• Quantum algorithm for finding minimum values in a Quantum Random Access Memory [0.0]
  The optimal classical deterministic algorithm can find the minimum value with a time complexity that grows linearly with the number of elements in the database. We propose a quantum algorithm for finding the minimum value of a database, which is quadratically faster than its best classical analogs.
  arXiv  Detail & Related papers  (2023-01-12T16:22:17Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• 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)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)

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.