Note that we can use compass and ruler to find the perpendicular bisector of two given points. Thus, we can use this to locate the midpoint of two points, and draw the circle having a given segment as a diameter.

Construct the circles with diameter $PS$ and $QR$ respectively. Construct the midpoints $M$ and $N$ of $\overline{PS}$ and $\overline{QR}$ (using the perpendicular bisectors) such that $M$ and $N$ lie on the same side of $\ell$. Construct the intersection point $B$ of the line $MN$ and $(QNR)$, and construct the intersection point $D$ of the line $MN$ and $(PMS)$. Also, construct the intersection point $A$ of $PD$ and $RB$, and construct the intersection point $C$ of $SD$ and $QB$. We claim that $ABCD$ is the desired square.

By construction, we already know that $P$, $Q$, $R$, $S$ lie on $AD$, $BC$, $AB$, $CD$ respectively. Since $PS$ and $QR$ are diameters of the two circles, we easily obtain $\angle ADC = \angle ABC = 90^\circ$. Also, since $M$ and $N$ are the midpoints of $\overline{PS}$ and $\overline{QR}$, the line $BD$ bisects $\angle ADC$ and $\angle ABC$. It follows that
$$\angle ADB = \angle CDB = \angle ABD = \angle CBD = 45^\circ,$$
which implies $\angle BAD = \angle BCD = 90^\circ$. Also, as $\angle ABD = \angle ADB$, we obtain $AB = AD$. This proves $ABCD$ is a square.