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!

No abstract uploaded!

No abstract uploaded!

We consider amalgamated free product II_{1}factors$M$=$M$_{1*$B$}$M$_{2*$B$}… and use “deformation/rigidity” and “intertwining” techniques to prove that any relatively rigid von Neumann subalgebra$Q$⊂$M$can be unitarily conjugated into one of the$M$_{$i$}’s. We apply this to the case where the$M$_{$i$}’s are w-rigid II_{1}factors, with$B$equal to either$C$, to a Cartan subalgebra$A$in$M$_{$i$}, or to a regular hyperfinite II_{1}subfactor$R$in$M$_{$i$}, to obtain the following type of unique decomposition results, àla Bass–Serre: If$M$= ($N$_{1 * C}N_{2*$C$}…)^{$t$}, for some$t$> 0 and some other similar inclusions of algebras$C$⊂$N$_{$i$}then, after a permutation of indices, ($B$⊂$M$_{$i$}) is inner conjugate to ($C$⊂$N$_{$i$})^{$t$}, for all$i$. Taking$B$=$C$and $ M_{i} = {\left( {L{\left( {Z^{2} \rtimes F_{2} } \right)}} \right)}^{{t_{i} }} $ , with {$t$_{$i$}}_{$i$⩾1}=$S$a given countable subgroup of$R$_{+}^{*}, we obtain continuously many non-stably isomorphic factors$M$with fundamental group $ {\user1{\mathcal{F}}}{\left( M \right)} $ equal to$S$. For$B$=$A$, we obtain a new class of factors$M$with unique Cartan subalgebra decomposition, with a large subclass satisfying $ {\user1{\mathcal{F}}}{\left( M \right)} = {\left\{ 1 \right\}} $ and Out(M) abelian and calculable. Taking$B$=$R$, we get examples of factors with $ {\user1{\mathcal{F}}}{\left( M \right)} = {\left\{ 1 \right\}} $ , Out($M$) =$K$, for any given separable compact abelian group$K$.