Limitations of the Macaulay Matrix Approach for Using the HHL Algorithm to Solve Multivariate Polynomial Systems
Author
Jintai Ding, Vlad Gheorghiu, András Gilyén, Sean Hallgren, Jianqiang Li
Title
Limitations of the Macaulay Matrix Approach for Using the HHL Algorithm to Solve Multivariate Polynomial Systems
Description
Verifying a lower bound for a specific Maculay matrix of finite size
Category
Academic Articles & Supplements
Keywords
URL
http://www.notebookarchive.org/2022-02-1ec5yyv/
DOI
https://notebookarchive.org/2022-02-1ec5yyv
Date Added
2022-02-03
Date Last Modified
2022-02-03
File Size
42.27 kilobytes
Supplements
Rights
Redistribution rights reserved
Download
Open in Wolfram Cloud
Limitations of the Macaulay Matrix Approach for Using the HHL Algorithm to Solve Multivariate Polynomial Systems
Limitations of the Macaulay Matrix Approach for Using the HHL Algorithm to Solve Multivariate Polynomial Systems
Jintai Ding, Vlad Gheorghiu, András Gilyén, Sean Hallgren, Jianqiang Li
This notebook verifies a lower bound on the condition number of the Macaulay matrix up to a number n=50 of variables (can be changed as required by changing Range[1,50] to Range[1,n] below) by analyzing the Gram matrix of certain “symmetric vectors”. For the details of the construction see https://arxiv.org/abs/2111.00405.
In[]:=
GramTotal[n_,d_]:=Table[Table[Binomial[d,s]Binomial[i,s]Binomial[j,s]/Binomial[n,s],{s,1,Min[i,j]}]//Total,{i,1,n},{j,1,n}];GramMax[n_,d_]:=Table[Table[d^sBinomial[i,s]Binomial[j,s]/Binomial[n,s],{s,1,Min[i,j]}]//Total,{i,1,n},{j,1,n}];BoundMax[n_]:=2GramMax[n,3n]-Table[Min[i,j]^Min[i,j],{i,1,n},{j,1,n}];ParallelMap[(Print[#];#[[2]])&@Timing[{#,PositiveDefiniteMatrixQ[BoundMax[#]]}]&,Range[1,50],Method->"FinestGrained"]And@@((%//Flatten)[[#;;;;2]]&/@{1,2})[[2]]
(kernel 4)
{0.000743,{1,True}}
(kernel 3)
{0.000758,{2,True}}
(kernel 2)
{0.000985,{3,True}}
(kernel 1)
{0.001081,{4,True}}
(kernel 4)
{0.000695,{5,True}}
(kernel 3)
{0.000939,{6,True}}
(kernel 2)
{0.0017,{7,True}}
(kernel 1)
{0.002537,{8,True}}
(kernel 4)
{0.004804,{9,True}}
(kernel 3)
{0.005925,{10,True}}
(kernel 2)
{0.007769,{11,True}}
(kernel 1)
{0.009819,{12,True}}
(kernel 4)
{0.007138,{13,True}}
(kernel 3)
{0.008895,{14,True}}
(kernel 2)
{0.011199,{15,True}}
(kernel 1)
{0.014143,{16,True}}
(kernel 4)
{0.015475,{17,True}}
(kernel 2)
{0.022933,{19,True}}
(kernel 1)
{0.026079,{20,True}}
(kernel 3)
{0.019839,{18,True}}
(kernel 4)
{0.034834,{21,True}}
(kernel 2)
{0.042744,{22,True}}
(kernel 3)
{0.065441,{24,True}}
(kernel 1)
{0.055641,{23,True}}
(kernel 4)
{0.075435,{25,True}}
(kernel 2)
{0.088645,{26,True}}
(kernel 3)
{0.11307,{27,True}}
(kernel 1)
{0.124085,{28,True}}
(kernel 4)
{0.140254,{29,True}}
(kernel 2)
{0.166236,{30,True}}
(kernel 1)
{0.227984,{32,True}}
(kernel 3)
{0.193042,{31,True}}
(kernel 4)
{0.245707,{33,True}}
(kernel 2)
{0.280592,{34,True}}
(kernel 1)
{0.319376,{35,True}}
(kernel 3)
{0.363283,{36,True}}
(kernel 4)
{0.39097,{37,True}}
(kernel 2)
{0.461251,{38,True}}
(kernel 1)
{0.497761,{39,True}}
(kernel 3)
{0.559574,{40,True}}
(kernel 4)
{0.616856,{41,True}}
(kernel 2)
{0.704569,{42,True}}
(kernel 1)
{0.784422,{43,True}}
(kernel 3)
{0.874084,{44,True}}
(kernel 4)
{0.951161,{45,True}}
(kernel 2)
{1.05869,{46,True}}
(kernel 1)
{1.13877,{47,True}}
(kernel 3)
{1.30282,{48,True}}
(kernel 4)
{1.34761,{49,True}}
(kernel 2)
{1.42994,{50,True}}
Out[]=
{{1,True},{2,True},{3,True},{4,True},{5,True},{6,True},{7,True},{8,True},{9,True},{10,True},{11,True},{12,True},{13,True},{14,True},{15,True},{16,True},{17,True},{18,True},{19,True},{20,True},{21,True},{22,True},{23,True},{24,True},{25,True},{26,True},{27,True},{28,True},{29,True},{30,True},{31,True},{32,True},{33,True},{34,True},{35,True},{36,True},{37,True},{38,True},{39,True},{40,True},{41,True},{42,True},{43,True},{44,True},{45,True},{46,True},{47,True},{48,True},{49,True},{50,True}}
Out[]=
True
Cite this as: Jintai Ding, Vlad Gheorghiu, András Gilyén, Sean Hallgren, Jianqiang Li, "Limitations of the Macaulay Matrix Approach for Using the HHL Algorithm to Solve Multivariate Polynomial Systems" from the Notebook Archive (2022), https://notebookarchive.org/2022-02-1ec5yyv
Download
