Mutually unbiased bases as a commuting polynomial optimisation problem
- URL: http://arxiv.org/abs/2308.01879v1
- Date: Thu, 3 Aug 2023 17:14:22 GMT
- Title: Mutually unbiased bases as a commuting polynomial optimisation problem
- Authors: Luke Mortimer
- Abstract summary: We consider the problem of mutually unbiased bases as an optimization problem over the reals.
We use two methods, combining a number of optimization techniques.
We demonstrate that such an algorithm would eventually solve the open question regarding dimension 6 with finite memory.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of mutually unbiased bases as a polynomial
optimization problem over the reals. We heavily reduce it using known
symmetries before exploring it using two methods, combining a number of
optimization techniques. The first of these is a search for bases using
Lagrange-multipliers that converges rapidly in case of MUB existence, whilst
the second combines a hierarchy of semidefinite programs with branch-and-bound
techniques to perform a global search. We demonstrate that such an algorithm
would eventually solve the open question regarding dimension 6 with finite
memory, although it still remains intractable. We explore the idea that to show
the inexistence of bases, it suffices to search for orthonormal vector sets of
certain smaller sizes, rather than full bases. We use our two methods to
conjecture the minimum set sizes required to show infeasibility, proving it for
dimensions 3. The fact that such sub-problems seem to also be infeasible
heavily reduces the number of variables, by 66\% in the case of the open
problem, potentially providing an large speedup for other algorithms and
bringing them into the realm of tractability.
Related papers
- Towards exact algorithmic proofs of maximal mutually unbiased bases sets
in arbitrary integer dimension [0.0]
We explore the concept of Mutually Unbiased Bases (MUBs) in discrete quantum systems.
It is known that for dimensions $d$ that are powers of prime numbers, there exists a set of up to $d+1$ bases that form an MUB set.
However, the maximum number of MUBs in dimensions that are not powers of prime numbers is not known.
arXiv Detail & Related papers (2023-09-21T18:00:42Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
We introduce two oblivious mirror descent algorithms based on a complementary composite setting.
Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function.
We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
arXiv Detail & Related papers (2023-06-30T08:34:29Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems.
We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
arXiv Detail & Related papers (2023-02-03T03:19:14Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
We propose and analyze inexact regularized Newton-type methods for finding a global saddle point of emphcon unconstrained min-max optimization problems.
We show that the proposed methods generate iterates that remain within a bounded set and that the iterations converge to an $epsilon$-saddle point within $O(epsilon-2/3)$ in terms of a restricted function.
arXiv Detail & Related papers (2022-10-23T21:24:37Z) - On the Second-order Convergence Properties of Random Search Methods [7.788439526606651]
We prove that standard randomsearch methods that do not rely on second-order information converge to a second-order stationary point.
We propose a novel variant of negative curvature by relying only on function evaluations.
arXiv Detail & Related papers (2021-10-25T20:59:31Z) - Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
This work considers a large family of bandit problems where the unknown underlying reward function is non-concave.
Our algorithms are based on a unified zeroth-order optimization paradigm that applies in great generality.
We show that the standard optimistic algorithms are sub-optimal by dimension factors.
arXiv Detail & Related papers (2021-07-09T16:04:24Z) - Revisiting the Complexity Analysis of Conflict-Based Search: New
Computational Techniques and Improved Bounds [5.158632635415881]
State-of-the-art approach to computing optimal solutions is Conflict-Based Search (CBS)
We revisit the complexity analysis of CBS to provide tighter bounds on the algorithm's run-time in the worst-case.
arXiv Detail & Related papers (2021-04-18T07:46:28Z) - A Regularized Limited Memory BFGS method for Large-Scale Unconstrained
Optimization and its Efficient Implementations [0.0]
We propose a new limited memory BFGS (L-BFGS) method with a certain regularization technique.
We show its global convergence under the usual assumptions.
We also extend it with several techniques such as nonmonotone technique and simultaneous use of the Wolfe line search.
arXiv Detail & Related papers (2021-01-12T11:24:37Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc.
Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource.
We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
arXiv Detail & Related papers (2020-05-09T02:48:23Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
A fundamental component of neural network verification is the computation of bounds on the values their outputs can take.
We propose a novel approach based on Lagrangian Decomposition.
We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
arXiv Detail & Related papers (2020-02-24T17:55:10Z)
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.