Efficient quantum algorithms related to autocorrelation spectrum

DOI10.1007/978-3-030-35423-7_21MaRDI QIDQ2179405zbMATH OpenOpenAlexFDO

Authors Debajyoti Bera, Subhamoy Maitra, Sapv Tharrmashastha

Publication date 12 May 2020

Full work available at URL https://arxiv.org/abs/1808.04448

zbMATH Keywords

autocorrelationBoolean functioncryptologyquantum computingWalsh spectrum

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Cryptography (94A60)

Abstract: In this paper, we propose efficient probabilistic algorithms for several problems regarding the autocorrelation spectrum. First, we present a quantum algorithm that samples from the Walsh spectrum of any derivative of $f()$. Informally, the autocorrelation coefficient of a Boolean function $f()$ at some point $a$ measures the average correlation among the values $f(x)$ and $f(xoplusa)$. The derivative of a Boolean function is an extension of autocorrelation to correlation among multiple values of $f()$. The Walsh spectrum is well-studied primarily due to its connection to the quantum circuit for the Deutsch-Jozsa problem. We extend the idea to "Higher-order Deutsch-Jozsa" quantum algorithm to obtain points corresponding to large absolute values in the Walsh spectrum of a certain derivative of $f()$. Further, we design an algorithm to sample the input points according to squares of the autocorrelation coefficients. Finally we provide a different set of algorithms for estimating the square of a particular coefficient or cumulative sum of their squares.

Recommendations

• Quantum algorithms for learning Walsh spectra of multi-output Boolean functions
• THE DEUTSCH–JOZSA ALGORITHM REVISITED IN THE DOMAIN OF CRYPTOGRAPHICALLY SIGNIFICANT BOOLEAN FUNCTIONS
• Quantum algorithms on Walsh transform and Hamming distance for Boolean functions
• Quantum algorithms for the Goldreich-Levin learning problem
• Polynomial-time quantum algorithms for finding the linear structures of Boolean function

Cites work

• An efficient quantum collision search algorithm and implications on symmetric cryptography
• Applying Grover's algorithm to AES: quantum resource estimates
• Breaking symmetric cryptosystems using quantum period finding
• Construction of \(n\)-variable \((n\equiv 2\bmod 4)\) balanced Boolean functions with maximum absolute value in autocorrelation spectra \(<2^{\frac{n}{2}}\)
• Grover meets Simon -- quantumly attacking the FX-construction
• Higher Order Derivatives and Differential Cryptanalysis
• scientific article; zbMATH DE number 1088929 (Why is no real title available?)
• scientific article; zbMATH DE number 774007 (Why is no real title available?)
• Observing biases in the state: case studies with Trivium and Trivia-SC
• Quantum algorithms on Walsh transform and Hamming distance for Boolean functions
• Rapid solution of problems by quantum computation
• THE DEUTSCH–JOZSA ALGORITHM REVISITED IN THE DOMAIN OF CRYPTOGRAPHICALLY SIGNIFICANT BOOLEAN FUNCTIONS

Cited in

(5)

• Quantum algorithms for learning Walsh spectra of multi-output Boolean functions
• Quantum cryptographic property testing of multi-output Boolean functions
• A quantum algorithm to estimate the Gowers \(U_2\) norm and linearity testing of Boolean functions
• Following forrelation -- quantum algorithms in exploring Boolean functions' spectra
• Introducing nega-forrelation: quantum algorithms in analyzing nega-Hadamard and nega-crosscorrelation spectra

This page was built for publication: Efficient quantum algorithms related to autocorrelation spectrum

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2179405)