hpqc-labs / book_about_quadratization Goto Github PK

• SFR-BCR-5 needs to be removed because Elisabeth says it's the exact same as SFR-BCR-4. I haven't removed it yet because I didn't want the page numbers to get messed up by removing pages (until some of the emails I've written which referred to specific page numbers, are read).
• SFR-BCR-3 and SFR-4 are just two special cases of SFR-8. Think about whether it's valuable to keep them. We have indeed kept PTRs which are just special cases of SFRs
• SFR-BCR-3 and SFR-4 are two cases of Theorem 1 (says Elisabeth) but I've labeled them as special cases of Theorem 2 (SFR-1 and 2 were labeled as Theorem 1, so surely SFR-3 and 4 should be Theorem 2?)
• SFR-BCR-7 is the same as SFR-BCR-5. One page needs to be removed (but remember that the version in [17] has a typo that was corrected in [26]
• SFR-BCR-1 and SFR-2 can be combined into one equation just like SFR-3 and SFR-4 (but no one has done it yet, because these require 1 more auxiliary than SFR-BCR-3 & 4 anyway).
• PTR-BCR-6: Elisabeth says there's only one quadratization using log(n) variables (which is PTR-BCR-3), but in my response I pointed out that Remark 5 from [26] seems to use log(n).
• PTR-BCR-1: is from Theorem 4.3 of [12] not from [17] ? It is also for even 'k' and not odd 'k' ? There's a missing coefficient of 2 ? However my response email to Elisabeth says that it does seem to be for odd 'k', so this is something to look at more thoroughly.
• PTR-BCR-2: I had this for only m= k/4, but it should actually be for a range of auxiliaries. While changing this, I noticed that I seem to have n's instead of k's in the matrix. This whole page needs to be checked thoroughly.

For "symmetric function reduction" gadgets, the examples are almost always just copied and pasted from some previous page. Now that Tin has derived the polynomial expressions for most of these types of functions, we can give concrete examples of these quadratizations being applied.

Examples are ideally written in only 1 line, and without too much notation apart from b_i and b_{a_i}, as in this case:

This might mean we need to pick k and N small for the EKON/AKON functions. If the functions still have to be huge, we can have the degree-k function on one line, and the quadratic function on the next line.

It seems it works even without the t^2 term and with the t term just equal to z instead of t.

The alternative form of KKR is working, but not the version in our "summary" section.

• https://link.springer.com/article/10.1007/s11590-019-01460-7
• https://arxiv.org/pdf/1109.2304.pdf
• https://link.springer.com/article/10.1007/s10601-009-9078-z
• https://arxiv.org/abs/1901.07636, and embedding version.
• https://www.sciencedirect.com/science/article/pii/0166218X85900356 (1985 paper quadratizing cubic submodular functions)
• https://inf.ethz.ch/personal/ladickyl/ray_cvpr15.pdf
• https://inf.ethz.ch/personal/ladickyl/ahcrf_pami13.pdf
• https://inf.ethz.ch/personal/ladickyl/cooc_ijcv12.pdf
• https://inf.ethz.ch/personal/ladickyl/robust_ijcv09.pdf
• Exact inference in multi-label CRFs with higher order cliques, CVPR 2008
• Kohli, MP Kumar, Torr, P3 & beyond: Solving energies with higher order cliques, in: CVPR, 2007, pp. 1-8.
• Refs in Section 8 of Ramalingam (2007)
• Ishikawa 2003 and 2009? Also "Kohli et al. [15], [14] extended the class of energies for which the optimal -expansion and swap moves can be computed in polynomial time. Komodakis and Paragios [19] employed a master-slave decomposition framework to solve a dual relaxation to the MRF problem. Rother et al. [33] used a soft-patternbased representation of higher-order functions that may for some energies lead to very compact first-order functions with a small number of nonsubmodular terms, as well as addressing the problem of transforming general multilabel functions into quadratic ones"
• https://dl.acm.org/doi/pdf/10.1145/3377930.3390144

• Compile LaTeX for SFR derivations and push PDF to the repository
• Compile Book and push PDF to the repository
• Add extra details into SFR derivations PDF for SFR-BCR 1,2,3,4
• Replace page for Remark 5 from Compact quads 2018 paper, into Book (add summary and example) (2 hours)
• Type up PTR derivations in LaTeX for PTR-BCR-1-6 (3-4 hours)
• Add Theorem 6 and paragraphs between Thm 6 and 7, from older BCR paper, to book, if it's not there yet. (2 hours)
• PTR-BCR-2, auxiliary variables should no be k/4, but should be between k/4 and k/2.
• Bibliography for Derivations PDF (2 hours)
• Go through both BCR papers, ABCG papers, and ERH thesis thoroughly to confirm confidently that all quads are in book, and book has no duplicates (8 hour)
• For each quad that isn't yet in the book (or derived in a PDF) type it up (1.5 hours/quad)
• Investigate ZZZ-TI-CBBK alpha equations, why does eqnarray mode take up so much more space than Table mode, and is there a workaround, so that we can have eqnarray (because table environment is not really MEANT for equations like this) while having the same spacing as the table environment.

Tuesday 19 January, Matthew emails Nike a progress report.
Next task is updating the book with the brand new quads from 2021.

• Respond to comment here: 57a732c#comments

1. Improve Introduction (including addition of a quadratic that has same ground state as the quantum cubic example)
2. Examples for:

• NTR-ABCG (should be called NTR-ABCG-1)
• NTR-ABCG-2
• PTR-BCR-1
• PTR-BCR-2
• PTR-BCR-3
• PTR-BCR-4
• PTR-KZ
• PTR-KZ (z version)
• SFR-ABCG-1

3. Asymmetric Cubic Reduction example is written in a slightly different format from the previous examples. (Same with the Alternative Forms subsection of this section). Please do not delete this comment until all examples and "alternative forms" are consistent throughout the book.
4. Add "reproduces the full spectrum" as a "pro" for all methods that do, which includes "Asymmetric Cubic Reduction"
5. RBL-2016,

• T should be t_a.
• There is no description of the transformation in the summary section
• There is no example given.
• Eq. 37 in https://github.com/k-local-quadratization/review/blob/6248e11ded86d514745d6f06f03ebfd1263a3ade/k-local-review.pdf has z on the left and b on the right.
• Needs to be verified
• Binomial squared has to be expanded

6. Alternative forms for all methods such that everything is in the "tableau"/matrix form

7. Asymmetric Reduction: Why is there 4 equations instead of 3, and why is the 3rd equation slightly indented?

8. Deduc-Reduc where we kill negative cubic terms (can even be generalized to higher order, and quadraitcs, and linear?)

9. Deduc-Reduc where we kill positive terms but require pre-/post-processing to rule out the artificially low ground states which do not satisfy the deducs.

10. Groebner bases method that Richard originally had, rather than this example which is from Emile's January 2015 work. 1-Qubit's paper was more similar to what Richard originally had.

11. Example of "application of ELM"

12. Method for using "strong quadratizations" for reducing multiple terms at once

13. z versions of all b methods, and b versions of all z methods

14. Feynman Hamiltonian would normally have many values of t, really it should say "The Feynman Hamiltonian contains 4-local Hamiltonians of the form:" (suggestion by Elizabeth Crosson was "Each term can be written in the form:" but really it's "each term plus its conjugate" so I have changed it to the sentence given here).

Add:
FGBZ can be used for more than one term, it's a pro!
Also add 2015 paper of FGBZ, we have cited 2011 one which is just the conference version
2-cover / pairwise-cover: ABCZ 2016 (one with the bounds), proof of upper bound: Remark 2, there is another quadratization method!!!

Add:
YY gadget to 2 -> 2 gadgets.

• need an example for negative term FGBZ
• "In combination with \ref{subsec:Negative-Monomial-Reduction}, it can reduce $t$ positive terms of degree $k$ in $n$ variables using $n+t(k-1)$ auxiliary variables in the worst case." applies to positive-term FGBZ, but needs to be modified for negative-term FGBZ.
• Summary and Example sections need to be re-done from scratch for Pairwise Covers

• Do we have Eq. 4 and Proposition 1 and 2 of https://personal.lse.ac.uk/anthony/Quadratization_web.pdf in the book? Also same paper says " to quadratize in polynomial time any pseudo-Boolean function while only using O(n|F|) auxiliary variables" -- do we have that? Also check Remark 1 (Bucheim and Rinaldi)
• Example on opening page, b1b2 comes up twice: b1b2 - 4b1b2 = -3b1b2
• -4b1b2b3 -> -4(b1b2 + b1b3), is something like that possible? Think about example on Pg 1 more. Eq. 2 can be transformed from Eq. 1 very easily, how general can we do that?
• "approximate ELCs" which Andreas found to be like my "heuristic gadgets"
• change font of Pauli matrices. (not sure what I meant there, and don't have time to check what time that was written and compare it to when the last font change was made, but now in January 2021 I think perhaps the goal was to straighten up the letters so they take up less space? This is after they were already switched from "math font" to a straighter font, but they're still a bit tilted)
• example on page 1 for quantum case only has coefficients of 1. Some negatives and non-1 numbers would be nice.
• quantum example preserves entire spectrum, but I don't want people to think right from page 1 that the entire spectrum needs to be preserved. Perhaps an example that only preserves the round state would be better pedagogically.
• deduc-reduc. Con: only preserves ground state (and degeneracy?). Can we generalize it to a full-spectrum version?
• split-reduc: "At this point, we could split H0 again, ...." think about what this sentence means.
• NTR-ABCG: see comments in .tex.
• NTR-AC: example and alternative forms don't look right.
• NTR-RBL: alternative form is quartic not cubic? Also I have a note saying "Eq. 10. i+2 = j" for the bibliography section.
• PTR-RBL-(3->2): alternative form is quartic but should just be expanded version of 74. Eq. 74 shoudl be Eq. 11 of RBL i+2=j which is apparently not the case.
• PTR-RBL-(4->2): apprently Eq. 11, i+2 < j, whatever that means (this is just what it says in my rough notes). Example has -z1z2z3z4 but it should be positive.
• Follow PENCIL NOTES in Nike's printed version, for FGBZ.
• Describe strategies for choosing coeffs in pairwise covers and Rosenberg
• Add Rosenberg-like method from Gruber's thesis.
• KKR(3->2) needs bibliography section!
• added Alavi's paper but he told me it was an old idea so the original papers should also be added.
• Figure out what was meant by "Can reduce the connectivity of an objective function, as it breaks interactions between variables." for FGBZ
• 2017 ABCG paper appears twice in bibliography (probably one of them was meant to be a 2015 arXiv or something? ) figure out why and make sure all references to these are not erroneous.
• Add https://arxiv.org/abs/math/0103170

• Cite Strandmark's Thesis (where, in the NTR-ABCG reduction?), find out whether the quadratization of Strandmark's Thesis (page 29 right before section 3.6 has been published in a paper)
• Figure out whether Gallagher, Batra and Parikh have different quadratizations. Find out where to cite them.

lambda >>0, so lambda*[...] must be 0.
There cannot exist any term in [...] that is >0 because then lambda*[...] will not be 0.
Every term in [...] must be satisfied (i.e. must be 0).

H_AF = H_1
H_SAT = H_2

z1z2z3 -> H_2local

(b_not1,b_not2,b_not3) = (b_a1,2 , b_a2,2, b_a3,2)
(b_a4,1) = b_f, and b_a4,2 = b_not_f
b_a000,1 = b_a1
b_a001,1 = b_a2
...
b_a111,1 = b_a8

b_a000,2 = b_a_not1
b_a001,2 = b_a_not2
....

• PTR-BCR-3, matrix bottom-left corner was 2^(i +-2) and the +- should either be + or - but I don't know what. SFR_Derivations.pdf in the "everything_else" folder seems to show an even different formula. For now I've just changed the +- to i+j-2 since this is most likely what was meant.

https://arxiv.org/pdf/1510.01588.pdf

Change name to: PTR-RBL
z1z2z3z4 -> 4za*(z1+z2+z3+z4)+2*(z1z2+z1z3+z1z4+z2z3+z2z4+z3z4)+7;
Alternative forms: (2za + sum_i z_i)^2 -1
Note: original paper does not have the -1 !!!
Con: (2za + sum_i z_i)^2 -1 doesn't work for k=5, but maybe if we changed the coefficients it could.

Summary: Eq. 3, Eq4 means J = Ja, h = -J +q0, q0 range max and min are given on line after Eq. 4. h_i is given 4 lines above Eq. 4. https://www.nature.com/articles/s41534-017-0022-6.pdf

• NTR-ABCG2 comes from pg. 8 of 2016 ABCG discrete applied mathematics, but is not in the thesis. (thesis does NOT say it has only prime factorizations, so it should have NTR-ABCG-2 ?)
• Add the form of 2016 paper as an "alternative form" of ABCG-2.
• Is NTR-GBP really isomorphic?

Amherst University doesn't exist... there's UMass Amherst and Amherst College.