Quantum algorithms on Walsh transform and Hamming distance for Boolean functions

DOI10.1007/s11128-018-1885-yzbMath1448.81261OpenAlexW2799840285WikidataQ129908787 ScholiaQ129908787MaRDI QIDQ1993748

Zheng-Wei Xie, Guangya Cai, Dao Wen Qiu

Publication date: 5 November 2018

Published in: Quantum Information Processing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11128-018-1885-y

zbMATH Keywords

quantum algorithmsHamming distanceWalsh transformBernstein-Vazirani algorithmquantum amplitude estimation

Mathematics Subject Classification ID

Quantum computation (81P68) Boolean functions (06E30) General theory of distance geometry (51K05) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (7)

Efficient quantum algorithms related to autocorrelation spectrum ⋮ Distributed Bernstein-Vazirani algorithm ⋮ Solving the learning parity with noise problem using quantum algorithms ⋮ A quantum algorithm to estimate the Gowers \(U_2\) norm and linearity testing of Boolean functions ⋮ Quantum algorithms for learning Walsh spectra of multi-output Boolean functions ⋮ Quantum cryptographic property testing of multi-output Boolean functions ⋮ Solving Bernstein and Vazirani's problem with the 2-bit permutation function

Cites Work

• Application of Grover's algorithm to check non-resiliency of a Boolean function
• Complexity measures and decision tree complexity: a survey.
• A quantum algorithm for approximating the influences of Boolean functions and its applications
• An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube
• The quantum query complexity of approximating the median and related statistics
• Forrelation
• Constructions of Resilient S-Boxes With Strictly Almost Optimal Nonlinearity Through Disjoint Linear Codes
• Linearity testing in characteristic two
• Property testing and its connection to learning and approximation
• Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces
• Exact quantum algorithm to distinguish Boolean functions of different weights
• Improving the Lower Bound on the Higher Order Nonlinearity of Boolean Functions With Prescribed Algebraic Immunity
• Quantum Complexity Theory
• Separations in Query Complexity Based on Pointer Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Quantum algorithms on Walsh transform and Hamming distance for Boolean functions