Recently Chen and Gao~\cite{ChenGao2017} proposed a new quantum algorithm for Boolean polynomial system solving, motivated by the cryptanalysis of some post-quantum cryptosystems. The key idea of their approach is to apply a Quantum Linear System (QLS) algorithm to a Macaulay linear system over $\CC$, which is derived from the Boolean polynomial system. The efficiency of their algorithm depends on the condition number of the Macaulay matrix. In this paper, we give a strong lower bound on the condition number as a function of the Hamming weight of the Boolean solution, and show that in many (if not all) cases a Grover-based exhaustive search algorithm outperforms their algorithm. Then, we improve upon Chen and Gao's algorithm by introducing the Boolean Macaulay linear system over $\CC$ by reducing the original Macaulay linear system. This improved algorithm could potentially significantly outperform the brute-force algorithm, when the Hamming weight of the solution is logarithmic in the number of Boolean variables. Furthermore, we provide a simple and more elementary proof of correctness for our improved algorithm using a reduction employing the Valiant-Vazirani affine hashing method, and also extend the result to polynomial systems over $\FF_q$ improving on subsequent work by Chen, Gao and Yuan \cite{ChenGao2018}. We also suggest a new approach for extracting the solution of the Boolean polynomial system via a generalization of the quantum coupon collector problem \cite{arunachalam2020QuantumCouponCollector}.

No abstract uploaded!

Let F be a foliation in a closed 3-manifold with negatively curved fundamental group and suppose that F is almost trans- verse to a quasigeodesic pseudo-Anosov °ow. We show that the leaves of the foliation in the universal cover extend continuously to the sphere at in¯nity; therefore the limit sets of the leaves are continuous images of the circle. One important corollary is that if F is a Reebless, ¯nite depth foliation in a hyperbolic 3-manifold, then it has the continuous extension property. Such ¯nite depth foliations exist whenever the second Betti number is non zero. The result also applies to other classes of foliations, including a large class of foliations where all leaves are dense, and in¯nitely many examples with one sided branching. One extremely useful tool is a detailed understanding of the topological structure and asymptotic properties of the 1-dimensional foliations in the leaves of e F induced by the stable and unstable foliations of the °ow.

No abstract uploaded!

We construct natural virtual fundamental classes for nested Hilbert schemes on a nonsingular projective surface S. This allows us to define new invariants of S that recover some of the known important cases such as Poincare invariants of Durr-Kabanov-Okonek and the stable pair invariants of Kool-Thomas. In the case of the nested Hilbert scheme of points, we can express these invariants in terms of integrals over the products of Hilbert scheme of points on S, and relate them to the vertex operator formulas found by Carlsson-Okounkov. The virtual fundamental classes of the nested Hilbert schemes play a crucial role in the Donaldson-Thomas theory of local-surface-threefolds that we study in [GSY17b].