Explaining Quadratic Arithmetic programs

This article is greatly inspired by Vitalik explanation on Quadratic arithmetic programs(QAPs). In this article we are going to take a direct approach to understand the complex step in making snarks or you may say that the first step of representing the massive state data into a low degree polynomial. If you are not familiar with the basics of polynomials and what benefits do they really offer? you may refer to this article.

To begin with, we must know that ZK-snarks are not applicable to any computational problem. There are few NP problems(such as boolean satisfiability) which are computationally infeasible to verify.

When we say that every NP problem has zero-knowledge proof, what we mean is that any NP problem instance can be proven to be true in ZK. This is what Goldreich, Micali and Wigderson explained in their paper . So to operate the problem we first have to convert the problem into a right form. This form is termed as Quadratic Arithmetic Program. This step is separate and will run in parallel alongside the zero-knowledge proof creation and its verification. The flow of QAP is program→circuit→R1CS→QAP.
To learn about more read upon this link.