quil-lang / quilc

The optimizing Quil compiler.
Apache License 2.0
449 stars 73 forks source link

Improve handling of multiply-controlled rotations #853

Open braised-babbage opened 1 year ago

braised-babbage commented 1 year ago

I was playing around with things like CONTROLLED CONTROLLED Z 0 1 2 and noticed that the behavior of Quilc is very sensitive to the specific choice of single qubit gate. For example, consider the following session

CL-QUIL> (defun compile-and-count-2q (gate n &optional (architecture :cz))
       (let* ((program (parse-quil 
                (with-output-to-string (s)
                 (dotimes (i n)
                   (write-string "CONTROLLED " s))
                 (write-string gate s)
                 (dotimes (i (1+ n))
                   (format s " ~D" i)))))
          (chip (build-nq-fully-connected-chip (1+ n) :architecture architecture))
          (compiled (compiler-hook program chip)))
         (loop :for instr :across (parsed-program-executable-code compiled)
           :when (and (typep instr 'gate-application) (< 1 (length (application-arguments instr))))
             :sum 1)))
CL-QUIL> (compile-and-count-2q "Z" 4)
WARNING:
   Complex determinant found for a matrix expected to be (real) orthogonal: det=#C(-0.36986434381890937d0 0.9290857695452064d0)
36
CL-QUIL> (compile-and-count-2q "X" 4)
WARNING:
   Complex determinant found for a matrix expected to be (real) orthogonal: det=#C(-0.9999077334728095d0 -0.013583981053760963d0)
WARNING:
   Complex determinant found for a matrix expected to be (real) orthogonal: det=#C(-0.08258079373873856d0 0.9965843729988346d0)
WARNING:
   Complex determinant found for a matrix expected to be (real) orthogonal: det=#C(-0.060783424164974155d0 -0.9981509782326426d0)
272

Since X = HZH, one would hope for less disparity between these two numbers.

The behavior is also sensitive to Z vs RZ(pi) and so on,

CL-QUIL> (compile-and-count-2q "RZ(pi)" 4)
38
CL-QUIL> (compile-and-count-2q "RX(pi)" 4)
WARNING:
   Complex determinant found for a matrix expected to be (real) orthogonal: det=#C(-0.04615463033526238d0 -0.9989343071987344d0)
WARNING:
   Complex determinant found for a matrix expected to be (real) orthogonal: det=#C(-0.04615463033526238d0 -0.9989343071987344d0)
WARNING:
   Complex determinant found for a matrix expected to be (real) orthogonal: det=#C(-0.04615463033526238d0 -0.9989343071987344d0)
WARNING:
   Complex determinant found for a matrix expected to be (real) orthogonal: det=#C(-0.1867653035669694d0 0.9824045609541608d0)
WARNING:
   Complex determinant found for a matrix expected to be (real) orthogonal: det=#C(-0.14002873640189503d0 -0.990147440021782d0)
294

I realize these are somewhat special cases, but it would be nice to handle them a bit better. For a very naive bound, one can refer to Theorem 8 of https://arxiv.org/pdf/quant-ph/0406176.pdf (this could even be implemented as an explicit define-compiler). There are probably even better bounds out there.

stylewarning commented 1 year ago

I should probably tone down the warnings too.