Dual bounds for the positive definite functions approach to mutually unbiased bases

• URL: http://arxiv.org/abs/2202.13259v1
• Date: Sun, 27 Feb 2022 01:06:56 GMT
• Title: Dual bounds for the positive definite functions approach to mutually unbiased bases
• Authors: Afonso S. Bandeira, Nikolaus Doppelbauer, Dmitriy Kunisky
• Abstract summary: A long-standing open problem asks if there can exist 7 mutually unbiased bases (MUBs) in $mathbbC6$. We prove that such a method of a degree at most 6 cannot exist.
• Score: 6.6673883720496425
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A long-standing open problem asks if there can exist 7 mutually unbiased bases (MUBs) in $\mathbb{C}^6$, or, more generally, $d + 1$ MUBs in $\mathbb{C}^d$ for any $d$ that is not a prime power. The recent work of Kolountzakis, Matolcsi, and Weiner (2016) proposed an application of the method of positive definite functions (a relative of Delsarte's method in coding theory and Lov\'{a}sz's semidefinite programming relaxation of the independent set problem) as a means of answering this question in the negative. Namely, they ask whether there exists a polynomial of a unitary matrix input satisfying various properties which, through the method of positive definite functions, would show the non-existence of 7 MUBs in $\mathbb{C}^6$. Using a convex duality argument, we prove that such a polynomial of degree at most 6 cannot exist. We also propose a general dual certificate which we conjecture to certify that this method can never show that there exist strictly fewer than $d + 1$ MUBs in $\mathbb{C}^d$.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• The Differential and Boomerang Properties of a Class of Binomials [28.489574654566677]
  We study the differential and boomerang properties of the function $F_2,u(x)=x2big (1+ueta(x)big)$ over $mathbbF_q$. We disproving a conjecture proposed in citebudaghyan2024arithmetization which states that there exist infinitely many $q$ and $u$ such that $F_2,u$ is an APN function.
  arXiv  Detail & Related papers  (2024-09-21T23:33:00Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  We study the power of query access for the task of agnostic learning under the Gaussian distribution. We show that query access gives significant runtime improvements over random examples for agnostically learning MIMs.
  arXiv  Detail & Related papers  (2023-12-27T15:50:47Z)
• Dimension-free Remez Inequalities and norm designs [48.5897526636987]
  A class of domains $X$ and test sets $Y$ -- termed emphnorm -- enjoy dimension-free Remez-type estimates. We show that the supremum of $f$ does not increase by more than $mathcalO(log K)2d$ when $f$ is extended to the polytorus.
  arXiv  Detail & Related papers  (2023-10-11T22:46:09Z)
• A polynomial quantum computing algorithm for solving the dualization problem [75.38606213726906]
  Given two monotone prime functions $f:0,1n to 0,1$ and $g:0,1n to 0,1$ the dualization problem consists in determining if $g$ is the dual of $f$. We present a quantum computing algorithm that solves the decision version of the dualization problem in time.
  arXiv  Detail & Related papers  (2023-08-28T18:12:54Z)
• Quantum and classical low-degree learning via a dimension-free Remez inequality [52.12931955662553]
  We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus. We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$. We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
  arXiv  Detail & Related papers  (2023-01-04T04:15:40Z)
• Construction of multipartite unextendible product bases and geometric measure of entanglement of positive-partial-transpose entangled states [0.0]
  We show that there exist two families UPBs in Hilbert space $mathbbC2otimesmathbbC2otimesmathbbC2otimesmathbbC2otimesmathbbC4$ by merging two different systems of an existing $7$-qubit UPB of size $11$. A new family of $7$-qubit positive-partial-transpose entangled states of rank $27-11$ is constructed.
  arXiv  Detail & Related papers  (2022-12-05T17:42:47Z)
• Mutually unbiased maximally entangled bases from difference matrices [0.0]
  Based on maximally entangled states, we explore the constructions of mutually unbiased bases in bipartite quantum systems. We establish $q$ mutually unbiased bases with $q-1$ maximally entangled bases and one product basis in $mathbbCqotimes mathbbCq$ for arbitrary prime power $q$.
  arXiv  Detail & Related papers  (2022-10-04T10:45:22Z)
• Mutually unbiased bases: polynomial optimization and symmetry [1.024113475677323]
  A set of $k$ orthonormal bases of $mathbb Cd$ is called mutually unbiased $|langle e,frangle |2 = 1/d$ whenever $e$ and $f$ are basis vectors in distinct bases. We exploit this symmetry (analytically) to reduce the size of the semidefinite programs making them tractable.
  arXiv  Detail & Related papers  (2021-11-10T14:14:53Z)
• Submodular + Concave [53.208470310734825]
  It has been well established that first order optimization methods can converge to the maximal objective value of concave functions. In this work, we initiate the determinant of the smooth functions convex body $$F(x) = G(x) +C(x)$. This class of functions is an extension of both concave and continuous DR-submodular functions for which no guarantee is known.
  arXiv  Detail & Related papers  (2021-06-09T01:59:55Z)
• Evidence for and against Zauner's MUB Conjecture in $\mathbb{C}^6$ [0.0]
  Zauner predicted that there can exist no more than three MUBs. In $mathbbC6$, not even a single vector has ever been found which is mutually unbiased to a set of three MUBs.
  arXiv  Detail & Related papers  (2021-03-15T20:29: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.