Multivariate quadratic equations
Solve a system of m quadratic equations in n variables over a specified finite field.
7 variants · 8 entries. Compare bounds only within the same variant.
COMPARISON VARIANTREGIME / INSTANCEENTRIESBEST c
MQBoolean · classical · worst caseClassical · ProvableDegree at most 2 over F_2; n variables; polynomially many explicitly represented equationsArbitrary Boolean quadratic systems30.6943 MQBoolean · classical · algebraic assumptionsClassical · Conditionalm=n quadratic equations over F_2 satisfying the source algebraic hypothesesAlgebraic regularity assumptions10.792 MQBoolean · quantum gates · algebraic assumptionsQuantum · Conditionalm=n quadratic equations over F_2; sequential quantum gate complexityAlgebraic regularity assumptions10.462 MQBoolean · quantum mesh · algebraic assumptionsQuantum · Conditionalm=n over F_2; mesh time exponent with an explicit area budgetMesh-connected quantum computation10.45743 MQF_3 · classical · worst caseClassical · ProvableFixed q=3, degree d=2, n variables, explicitly represented equationsArbitrary quadratic systems over F_310.696 MQF_4 · classical · worst caseClassical · ProvableFixed q=4, degree d=2, n variables, explicitly represented equationsArbitrary quadratic systems over F_410.698 MQOverdetermined · algebraic solversClassical · ConditionalQuadratic systems over F_q with fixed m/n > 1; q and density fixedSpecified equation density0—