More Like this

1. A higher dimensional Bourgain-Dyatlov fractal uncertainty principle

   Han, Rui; Schlag, Wilhelm (October 2019, Analysis & PDE)

   We establish a version of the fractal uncertainty principle, obtained by Bourgain and Dyatlov in 2016, in higher dimensions. The Fourier support is limited to sets Y⊂ℝd which can be covered by finitely many products of δ-regular sets in one dimension, but relative to arbitrary axes. Our results remain true if Y is distorted by diffeomorphisms. Our method combines the original approach by Bourgain and Dyatlov, in the more quantitative 2017 rendition by Jin and Zhang, with Cartan set techniques. 

   more » « less
2. Inversion formula and range conditions for a linear system related with the multi‐interval finite Hilbert transform in L ²

   https://doi.org/10.1002/mana.201800567  

   Katsevich, Alexander; Bertola, Marco; Tovbis, Alexander (June 2021, Mathematische Nachrichten)

   Abstract Givenndisjoint intervals on together withnfunctions , , and an matrix , the problem is to find anL²solution , , to the linear system , where , is a matrix of finite Hilbert transforms with defined on , and is a matrix of the corresponding characteristic functions on . Since we can interpret , as a generalized multi‐interval finite Hilbert transform, we call the formula for the solution as “the inversion formula” and the necessary and sufficient conditions for the existence of a solution as the “range conditions”. In this paper we derive the explicit inversion formula and the range conditions in two specific cases: a) the matrix Θ is symmetric and positive definite, and; b) all the entries of Θ are equal to one. We also prove the uniqueness of solution, that is, that our transform is injective. In the case a), that is, when the matrix Θ is positive definite, the inversion formula is given in terms of the solution of the associated matrix Riemann–Hilbert Problem. In the case b) we reduce the multi interval problem to a problem onncopies of and then express our answers in terms of the Fourier transform. We also discuss other cases of the matrix Θ. 

   more » « less
3. Injectivity of the Heisenberg X-ray transform

   https://doi.org/10.1016/j.jfa.2020.108886  

   Flynn, Steven (March 2021, Journal of Functional Analysis)

   We initiate the study of X-ray tomography on sub-Riemannian manifolds, for which the Heisenberg group exhibits the simplest nontrivial example. With the language of the group Fourier transform, we prove an operator-valued incarnation of the Fourier Slice Theorem, and apply this new tool to show that a sufficiently regular function on the Heisenberg group is determined by its line integrals over sub-Riemannian geodesics. We also consider the family of taming metrics $$g_\epsilon$$ approximating the sub-Riemannian metric, and show that the associated X-ray transform is injective for all $$\epsilon > 0$$. This result gives a concrete example of an injective X-ray transform in a geometry with an abundance of conjugate points. 

   more » « less
4. Quantum Fourier Transform Has Small Entanglement

   https://doi.org/10.1103/PRXQuantum.4.040318  

   Chen, Jielun; Stoudenmire, EM; White, Steven R (October 2023, PRX Quantum)

   The Quantum Fourier Transform (QFT) is a key component of many important quantum algorithms, most famously as being the essential ingredient in Shor's algorithm for factoring products of primes. Given its remarkable capability, one would think it can introduce large entanglement to qubit systems and would be difficult to simulate classically. While early results showed QFT indeed has maximal operator entanglement, we show that this is entirely due to the bit reversal in the QFT. The core part of the QFT has Schmidt coefficients decaying exponentially quickly, and thus it can only generate a constant amount of entanglement regardless of the number of qubits. In addition, we show the entangling power of the QFT is the same as the time evolution of a Hamiltonian with exponentially decaying interactions, and thus a variant of the area law for dynamics can be used to understand the low entanglement intuitively. Using the low entanglement property of the QFT, we show that classical simulations of the QFT on a matrix product state with low bond dimension only take time linear in the number of qubits, providing a potential speedup over the classical fast Fourier transform (FFT) on many classes of functions. We demonstrate this speedup in test calculations on some simple functions. For data vectors of length 106 to 108, the speedup can be a few orders of magnitude. 

   more » « less
5. Fourier Analysis-based Iterative Combinatorial Auctions

   https://doi.org/10.24963/ijcai.2022/78  

   Weissteiner, Jakob; Wendler, Chris; Seuken, Sven; Lubin, Ben; Püschel, Markus (July 2022, Thirty-First International Joint Conference on Artificial Intelligence)

   Recent advances in Fourier analysis have brought new tools to efficiently represent and learn set functions. In this paper, we bring the power of Fourier analysis to the design of combinatorial auctions (CAs). The key idea is to approximate bidders' value functions using Fourier-sparse set functions, which can be computed using a relatively small number of queries. Since this number is still too large for practical CAs, we propose a new hybrid design: we first use neural networks (NNs) to learn bidders’ values and then apply Fourier analysis to the learned representations. On a technical level, we formulate a Fourier transform-based winner determination problem and derive its mixed integer program formulation. Based on this, we devise an iterative CA that asks Fourier-based queries. We experimentally show that our hybrid ICA achieves higher efficiency than prior auction designs, leads to a fairer distribution of social welfare, and significantly reduces runtime. With this paper, we are the first to leverage Fourier analysis in CA design and lay the foundation for future work in this area. Our code is available on GitHub: https://github.com/marketdesignresearch/FA-based-ICAs. 

   more » « less