Extending Forrelation: Quantum Algorithms Related to Generalized Fourier-Correlation

• URL: http://arxiv.org/abs/2507.07231v1
• Date: Wed, 09 Jul 2025 19:06:46 GMT
• Title: Extending Forrelation: Quantum Algorithms Related to Generalized Fourier-Correlation
• Authors: Suman Dutta, Subhamoy Maitra, Pantelimon Stanica,
• Abstract summary: We study different cryptographically significant spectra of Boolean functions, including the Walsh-Hadamard, cross-correlation, and autocorrelation.<n>We present the most generalized version of the Deutsch-Jozsa algorithm, which extends the standard and previously extended versions.<n>We also discuss quantum algorithms in identifying the shifts between two bent (or negabent) functions with certain modifications.
• Score: 4.66313002591741
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study different cryptographically significant spectra of Boolean functions, including the Walsh-Hadamard, cross-correlation, and autocorrelation. The $2^k$-variation by Stanica [IEEE-IT 2016] is considered here with the formulation for any $m \in \mathbb{N}$. Given this, we present the most generalized version of the Deutsch-Jozsa algorithm, which extends the standard and previously extended versions, thereby encompassing them as special cases. Additionally, we generalize the Forrelation formulation by introducing the $m$-Forrelation and propose various quantum algorithms towards its estimation. In this regard, we explore different strategies in sampling these newly defined spectra using the proposed $m$-Forrelation algorithms and present a comparison of their corresponding success probabilities. Finally, we address the problem related to affine transformations of generalized bent functions and discuss quantum algorithms in identifying the shifts between two bent (or negabent) functions with certain modifications, and compare these with existing results.

Related papers

• Quantum Algorithms for Gowers Norm Estimation, Polynomial Testing, and Arithmetic Progression Counting over Finite Abelian Groups [0.0]
  We propose a family of quantum algorithms for estimating Gowers norms $ Uk $ over finite abelian groups.<n>These algorithms leverage recent inverse theorems for Gowers norms, together with amplitude estimation, to reveal higher-order correlations.
  arXiv  Detail & Related papers  (2025-08-02T06:58:12Z)
• Accelerated Extragradient-Type Methods -- Part 2: Generalization and Sublinear Convergence Rates under Co-Hypomonotonicity [6.78476672849813]
  This paper studies two types of extragradient-based methods: anchored extragradient and Nesterov's accelerated extragradient.<n>We unify and generalize a class of anchored extragradient methods for monotone inclusions to a wider range of schemes.<n>We propose another novel class of Nesterov's accelerated extragradient methods to solve inclusions.
  arXiv  Detail & Related papers  (2025-01-08T16:06:15Z)
• Variational Inference on the Boolean Hypercube with the Quantum Entropy [0.0]
  We derive variational inference upper-bounds on the log-partition function of pairwise Markov random fields on the Boolean hypercube.<n>We then propose an efficient algorithm to compute these bounds based on primal-dual optimization.
  arXiv  Detail & Related papers  (2024-11-06T08:42:53Z)
• Unified Framework for Matchgate Classical Shadows [0.0]
  Estimating quantum fermionic properties is a computationally difficult yet crucial task for the study of electronic systems. Recent developments have begun to address this challenge by introducing classical shadows protocols. We propose an approach that unifies these different protocols, proving their equivalence, and deriving from it an optimal sampling scheme.
  arXiv  Detail & Related papers  (2024-09-05T18:01:00Z)
• 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)
• 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)
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory [44.99833362998488]
  We introduce quantum algorithms that can efficiently simulate certain classes of interactions consisting of correlated changes in multiple quantum numbers. The lattice gauge theory studied is the SU(2) gauge theory in 1+1 dimensions coupled to one flavor of staggered fermions. The algorithms are shown to be applicable to higher-dimensional theories as well as to other Abelian and non-Abelian gauge theories.
  arXiv  Detail & Related papers  (2022-12-28T18:56:25Z)
• Alternatives to a nonhomogeneous partial differential equation quantum algorithm [52.77024349608834]
  We propose a quantum algorithm for solving nonhomogeneous linear partial differential equations of the form $Apsi(textbfr)=f(textbfr)$. These achievements enable easier experimental implementation of the quantum algorithm based on nowadays technology.
  arXiv  Detail & Related papers  (2022-05-11T14:29:39Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  We study a class of algorithms for solving bilevel optimization problems in both deterministic and deterministic settings. We exploit a warm-start strategy to amortize the estimation of the exact gradient. By using this framework, our analysis shows these algorithms to match the computational complexity of methods that have access to an unbiased estimate of the gradient.
  arXiv  Detail & Related papers  (2021-11-29T15:10:09Z)
• Following Forrelation -- Quantum Algorithms in Exploring Boolean Functions' Spectra [3.2498534294827044]
  We revisit the quantum algorithms for obtaining Forrelation values. We introduce the existing 2-fold Forrelation formulation with bent duality based promise problems. We tweak the quantum algorithm with superposition of linear functions to obtain a cross-correlation sampling technique.
  arXiv  Detail & Related papers  (2021-04-25T17:13:18Z)
• Robustly Learning Mixtures of $k$ Arbitrary Gaussians [47.40835932474677]
  We give a-time algorithm for the problem of robustly estimating a mixture of $k$ arbitrary Gaussians in $mathbbRd$, for any fixed $k$, in the presence of a constant fraction of arbitrary corruptions. Our main tools are an efficient emphpartial clustering algorithm that relies on the sum-of-squares method, and a novel tensor decomposition algorithm that allows errors in both Frobenius norm and low-rank terms.
  arXiv  Detail & Related papers  (2020-12-03T17:54:03Z)

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.