search

quil-lang / quilc

The optimizing Quil compiler.
Apache License 2.0
457 stars 72 forks source link

TEST-MEASURE-SEMANTICS: Expression (EVERY #'DOUBLE= (AMPLITUDES QVM) (AMPLITUDES QVM-COMP)) evaluated to false #284

Closed appleby closed 5 years ago

appleby commented 5 years ago

TEST-MEASURE-SEMANTICS fails for me when running make test. This is testing on master and after a make clean clean-cache.

TEST-MEASURE-SEMANTICS
Unhandled FIASCO::FAILED-ASSERTION in thread #<SB-THREAD:THREAD "main thread" RUNNING
                                                {10005205B3}>:
  Test assertion failed when running TEST-MEASURE-SEMANTICS:

Expression (EVERY #'DOUBLE= (AMPLITUDES QVM)
                  (AMPLITUDES QVM-COMP)) evaluated to false
0: #'DOUBLE= => #<FUNCTION CL-QUIL::DOUBLE=>
1: (AMPLITUDES QVM) => #(#C(1.0000000000000004d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                         #C(0.0d0 0.0d0) #C(0.0d0 0.0d0))
2: (AMPLITUDES QVM-COMP) => #(#C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.9999999999999998d0 -2.7755575615628914d-16)
                              #C(0.0d0 0.0d0)
                              #C(-1.2750049807168125d-16 2.572419573305391d-16)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0)
                              #C(0.0d0 0.0d0)
                              #C(-1.7341430856005275d-16 -2.724622353344712d-17)
                              #C(0.0d0 0.0d0)
                              #C(-3.92523114670944d-17 -8.326672684688675d-17))

Backtrace for: #<SB-THREAD:THREAD "main thread" RUNNING {10005205B3}>
0: (SB-DEBUG::DEBUGGER-DISABLED-HOOK #<FIASCO::FAILED-ASSERTION {1007952113}> #<unused argument> :QUIT T)
1: (SB-DEBUG::RUN-HOOK SB-EXT:*INVOKE-DEBUGGER-HOOK* #<FIASCO::FAILED-ASSERTION {1007952113}>)
2: (INVOKE-DEBUGGER #<FIASCO::FAILED-ASSERTION {1007952113}>)
3: (ERROR #<FIASCO::FAILED-ASSERTION {1007952113}>)
4: (SB-KERNEL:WITH-SIMPLE-CONDITION-RESTARTS ERROR NIL #<FIASCO::FAILED-ASSERTION {1007952113}>)
5: (FIASCO::RECORD-FAILURE FIASCO::FAILED-ASSERTION :FORM (IS (EVERY (FUNCTION CL-QUIL::DOUBLE=) (QVM::AMPLITUDES QVM) (QVM::AMPLITUDES QVM-COMP))) :FORMAT-CONTROL "Expression ~A evaluated to ~A~%~D: ~A => ~S~%~D: ~A => ~S~%~D: ~A => ~S" :FORMAT-ARGUMENTS ((EVERY #1=(FUNCTION CL-QUIL::DOUBLE=) #2=(QVM::AMPLITUDES QVM) #3=(QVM::AMPLITUDES QVM-COMP)) "false" 0 #1# #<FUNCTION CL-QUIL::DOUBLE=> 1 #2# #(#C(1.0000000000000004d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) ...) 2 #3# #(#C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) #C(0.0d0 0.0d0) ...)))
6: (%TEST-MEASURE-SEMANTICS "RX(pi/3) 0
CNOT 0 2
RX(7.330382858376184) 2
MEASURE 0
MEASURE 1
MEASURE 2
")
7: (CL-PERMUTATION:MAP-SPEC #<CLOSURE (LAMBDA (RANK WORD) :IN MAP-MEASURE-COMBINATIONS) {10055CAF1B}> #<CL-PERMUTATION:WORD-SPEC {10055CAED3}>)
8: ((LABELS FIASCO::RUN-TEST-BODY :IN FIASCO::RUN-TEST-BODY-IN-HANDLERS))
9: (FIASCO::CALL-WITH-TEST-HANDLERS #<CLOSURE (LAMBDA NIL :IN FIASCO::RUN-TEST-BODY-IN-HANDLERS) {100551740B}>)
10: (FIASCO::PRETTY-RUN-TEST #<test TEST-MEASURE-SEMANTICS> #<FUNCTION (LABELS TEST-MEASURE-SEMANTICS :IN TEST-MEASURE-SEMANTICS) {53EBA55B}>)
11: ((LABELS #:BODY-SYM0 :IN TEST-MEASURE-SEMANTICS))
12: (TEST-MEASURE-SEMANTICS)
13: ((LABELS FIASCO-SUITES::CL-QUIL-TESTS :IN FIASCO-SUITES::CL-QUIL-TESTS))
14: ((LABELS FIASCO::RUN-TEST-BODY :IN FIASCO::RUN-TEST-BODY-IN-HANDLERS))
15: (FIASCO::CALL-WITH-TEST-HANDLERS #<CLOSURE (LAMBDA NIL :IN FIASCO::RUN-TEST-BODY-IN-HANDLERS) {100D97A04B}>)
16: (FIASCO::PRETTY-RUN-TEST #<test FIASCO-SUITES::CL-QUIL-TESTS :tests 154> #<FUNCTION (LABELS FIASCO-SUITES::CL-QUIL-TESTS :IN FIASCO-SUITES::CL-QUIL-TESTS) {53E08A8B}>)
17: ((LABELS #:BODY-SYM1 :IN FIASCO-SUITES::CL-QUIL-TESTS))
18: (FIASCO-SUITES::CL-QUIL-TESTS)
19: (RUN-SUITE-TESTS #<test FIASCO-SUITES::CL-QUIL-TESTS :tests 154> :VERBOSE NIL :STREAM #<SYNONYM-STREAM :SYMBOL SB-SYS:*STDOUT* {1000006123}> :INTERACTIVE T)
20: (RUN-TESTS :CL-QUIL-TESTS :DESCRIBE-FAILURES T :VERBOSE NIL :STREAM #<SYNONYM-STREAM :SYMBOL SB-SYS:*STDOUT* {1000006123}> :INTERACTIVE T)
21: (RUN-CL-QUIL-TESTS :VERBOSE NIL :HEADLESS NIL)
22: ((SB-PCL::EMF ASDF/ACTION:PERFORM) #<unused argument> #<unused argument> #<ASDF/LISP-ACTION:TEST-OP > #<ASDF/SYSTEM:SYSTEM "cl-quil-tests">)
23: ((LAMBDA NIL :IN ASDF/ACTION:CALL-WHILE-VISITING-ACTION))
24: ((:METHOD ASDF/ACTION:PERFORM-WITH-RESTARTS :AROUND (T T)) #<ASDF/LISP-ACTION:TEST-OP > #<ASDF/SYSTEM:SYSTEM "cl-quil-tests">) [fast-method]
25: ((:METHOD ASDF/PLAN:PERFORM-PLAN (T)) #<ASDF/PLAN:SEQUENTIAL-PLAN {100C4836C3}>) [fast-method]
26: ((FLET SB-C::WITH-IT :IN SB-C::%WITH-COMPILATION-UNIT))
27: ((:METHOD ASDF/PLAN:PERFORM-PLAN :AROUND (T)) #<ASDF/PLAN:SEQUENTIAL-PLAN {100C4836C3}>) [fast-method]
28: ((:METHOD ASDF/OPERATE:OPERATE (ASDF/OPERATION:OPERATION ASDF/COMPONENT:COMPONENT)) #<ASDF/LISP-ACTION:TEST-OP > #<ASDF/SYSTEM:SYSTEM "cl-quil"> :PLAN-CLASS NIL :PLAN-OPTIONS NIL) [fast-method]
29: ((SB-PCL::EMF ASDF/OPERATE:OPERATE) #<unused argument> #<unused argument> #<ASDF/LISP-ACTION:TEST-OP > #<ASDF/SYSTEM:SYSTEM "cl-quil">)
30: ((LAMBDA NIL :IN ASDF/OPERATE:OPERATE))
31: ((:METHOD ASDF/OPERATE:OPERATE :AROUND (T T)) #<ASDF/LISP-ACTION:TEST-OP > #<ASDF/SYSTEM:SYSTEM "cl-quil">) [fast-method]
32: ((SB-PCL::EMF ASDF/OPERATE:OPERATE) #<unused argument> #<unused argument> ASDF/LISP-ACTION:TEST-OP :CL-QUIL)
33: ((LAMBDA NIL :IN ASDF/OPERATE:OPERATE))
34: ((:METHOD ASDF/OPERATE:OPERATE :AROUND (T T)) ASDF/LISP-ACTION:TEST-OP :CL-QUIL) [fast-method]
35: (ASDF/SESSION:CALL-WITH-ASDF-SESSION #<CLOSURE (LAMBDA NIL :IN ASDF/OPERATE:OPERATE) {100C41581B}> :OVERRIDE T :KEY NIL :OVERRIDE-CACHE T :OVERRIDE-FORCING NIL)
36: ((LAMBDA NIL :IN ASDF/OPERATE:OPERATE))
37: (ASDF/SESSION:CALL-WITH-ASDF-SESSION #<CLOSURE (LAMBDA NIL :IN ASDF/OPERATE:OPERATE) {100C381A3B}> :OVERRIDE NIL :KEY NIL :OVERRIDE-CACHE NIL :OVERRIDE-FORCING NIL)
38: ((:METHOD ASDF/OPERATE:OPERATE :AROUND (T T)) ASDF/LISP-ACTION:TEST-OP :CL-QUIL) [fast-method]
39: (ASDF/OPERATE:TEST-SYSTEM :CL-QUIL)
40: (SB-INT:SIMPLE-EVAL-IN-LEXENV (ASDF/OPERATE:TEST-SYSTEM :CL-QUIL) #<NULL-LEXENV>)
41: (EVAL (ASDF/OPERATE:TEST-SYSTEM :CL-QUIL))
42: (SB-IMPL::PROCESS-EVAL/LOAD-OPTIONS ((:LOAD . "/home/ma/opt/rigetti-quicklisp/setup.lisp") (:EVAL . "(push (truename \".\") asdf:*central-registry*)") (:EVAL . "(push :hunchentoot-no-ssl *features*)") (:EVAL . "(push :drakma-no-ssl *features*)") (:EVAL . "(push (truename \"../\") ql:*local-project-directories*)") (:EVAL . "(ql:quickload :cl-quil-tests)") (:EVAL . "(asdf:test-system :cl-quil)") (:EVAL . "(ql:quickload :quilc-tests)") (:EVAL . "(asdf:test-system :quilc)") (:QUIT)))
43: (SB-IMPL::TOPLEVEL-INIT)
44: ((FLET SB-UNIX::BODY :IN SB-EXT:SAVE-LISP-AND-DIE))
45: ((FLET "WITHOUT-INTERRUPTS-BODY-14" :IN SB-EXT:SAVE-LISP-AND-DIE))
46: ((LABELS SB-IMPL::RESTART-LISP :IN SB-EXT:SAVE-LISP-AND-DIE))

unhandled condition in --disable-debugger mode, quitting
;
; compilation unit aborted
;   caught 1 fatal ERROR condition
make: *** [Makefile:124: test] Error 1
appleby commented 5 years ago

Fails consistently for me, so if this is only happening on my machine, I will get around to debugging it eventually.

notmgsk commented 5 years ago

Passing for me. Strange

Mark Skilbeck Junior Quantum Engineer mark.skilbeck@rigetti.com rigetti.com

On Jun 12, 2019, at 3:32 PM, appleby notifications@github.com wrote:

Fails consistently for me, so if this is only happening on my machine, I will get around to debugging it eventually.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/rigetti/quilc/issues/284?email_source=notifications&email_token=AEAK273X2XLORYYXVHQRZK3P2F2P3A5CNFSM4HXTPTCKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXR7LCI#issuecomment-501478793, or mute the thread https://github.com/notifications/unsubscribe-auth/AEAK275KVFICRCBNPEUYASLP2F2P3ANCNFSM4HXTPTCA.

appleby commented 5 years ago

Passing for me. Strange

Possibly my vintage computing technology, then. As long as it's not bothering anyone else, I'll take my time. I had a quick look and there was a comment in there from @ecpeterson with a bunch of math stuff I didn't understand that ended with a "Caveat programmer." Probably start there unless someone tells me otherwise.

ecpeterson commented 5 years ago

Both arrays in the trace look like a MEASURE happened instead of a MEASURE-DISCARD. How up-to-date is the QVM that the tests are building against? These require it to be pretty close to GitHub master.

appleby commented 5 years ago

Bingo! That's a numberwang! Thank you for saving me from hours of looking for a bug that does not exist :).

Out-of-date QVM was the first thing I suspected/checked, but I forgot that my local repo now points at my fork at appleby/qvm, not rigetti/qvm, so when git pull told me "everything up to date", I foolishly believed it.

This feels like a learnable moment for me, so out of curiosity: how did you divine by staring at those amplitudes that a MEASURE was preformed, rather than MEASURE-DISCARD?

notmgsk commented 5 years ago

Bingo! That's a numberwang! Thank you for saving me from hours of looking for a bug that does not exist :).

Out-of-date QVM was the first thing I suspected/checked, but I forgot that my local repo now points at my fork at appleby/qvm, not rigetti/qvm, so when git pull told me "everything up to date", I foolishly believed it.

This feels like a learnable moment for me, so out of curiosity: how did you divine by staring at those amplitudes that a MEASURE was preformed, rather than MEASURE-DISCARD?

Because he's gosh darn wacky. During one conversation when we were debugging something, he made a similar point, something like "Well if you look here these two numbers look like +/- pi/7 and over here these two columns are clearly not orthogonal and ... and ...". Hopefully it's a skill we can all develop after looking at quilc stackframes for long enough.

By the way, I think the reason is that a MEASURE will collapse the quantum state -- this is evidenced by the above vectors having one and only one 1 and everything else 0 (ignoring small differences). MEASURE-DISCARD will not do the above. There is more subtlty here I think (namely that we're working with a density matrix) but that's the general idea.

appleby commented 5 years ago

By the way, I think the reason is that a MEASURE will collapse the quantum state -- this is evidenced by the above vectors having one and only one 1 and everything else 0 (ignoring small differences). MEASURE-DISCARD will not do the above. There is more subtlty here I think (namely that we're working with a density matrix) but that's the general idea.

That (surprisingly) makes sense. Thank you for ignoring the finer details and putting it in layman's terms for me :).

appleby commented 5 years ago

Now that my quantum lesson for the day is complete, I'm closing this and filing it under PEBKAC.

ecpeterson commented 5 years ago

Mark is spot on in his second paragraph. What follows is an explanation of why:

One of the features of an ordinary "wavefunction" (or "pure state") in quantum computing, as represented by the QVM as a vector of complex values, is superposition. A wavefunction that looks like (1/sqrt(2), 1/2, 1/2, 0) is understood as being composed of pieces: there's 1/sqrt(2) that belongs to |00>, 1/2 that belongs to |01>, and 1/2 that belongs to |10>. The physical meaning of these numbers is that if you query the computer—viz., if you MEASURE it and examine the resulting bits of output—then you'll see the bitstrings 00, 01, and 10 with respective probabilities |1/sqrt(2)|^2 = 1/2, |1/2|^2 = 1/4, and |1/2|^2 = 1/4. Additionally, MEASURE has the relatively unique property of being an irreversible operation: depending on which bitstring you see after a measurement, the wavefunction itself gets replaced by (1, 0, 0, 0), (0, 1, 0, 0), or (0, 0, 1, 0).

There's an alternative formalism for tracking the state of a quantum computer, called the "density matrix", which has two main benefits:

  1. It's suitable for studying "open" quantum systems, where there's a hidden actor whose behavior you don't understand or who steals away information from your system (e.g.: noise in a system).
  2. It's suitable for studying combinations of states in a sense somewhat different from ordinary superposition: with ordinary superposition, you can rotate a state into and out of superposition with reversible operations (e.g.: H 0; CNOT 0 1 moves you from |00> to 1/sqrt(2) |00> + 1/sqrt(2) |11>, but then doing CNOT 0 1; H 0 will move you right back to |00>). However, you can see some superposition-like effects by taking more literal combinations of states, saying: I'm going to run two QVMs simultaneously, and whatever I do to one I'll do to the other, but I'm going to start them from different places, and when I'm finally asked to MEASURE, I'll reply with one of the two measurements that I get by flipping an additional coin and choosing which of the two secret QVM's replies to return based on that.[1] This kind of "superposition" is orthogonal to the first kind: if you start with two QVMs in different states, then (I think!) no sequence of operations, applied according to the protocol above, will end up putting them in the same state (so that they behave like a single 'pure' QVM). (You can, however, get a single pure-state QVM to behave like this ensemble of QVMs just by re-running a program through the single pure-state QVM many many times. This is, in fact, how we simulate noise on the pure-state QVM.)

The precise mathematical mechanism by which density matrices accomplish this isn't so important. It's more complicated than literally taking formal sums of pure-state things, but I'd advise you to not worry about it until later.

As for what this has to do with us, MEASURE itself has properties relevant to the density matrix formalism: MEASURE reveals information about a quantum system, previously considered to be isolated, to an outside observer, and so can be studied from the same perspective of 'information loss' as is used with noise. It also feels like it splits a single pure-state QVM apart into two pieces (or, if you like, two worlds): one where the QVM replied with 0 (weighted by whatever probability) and one where the QVM replied with 1 (weighted with the complementary probability). The main trouble with making all the pieces in this conversation thus far line up is that, because the QVM tells you which bit it measured you, can you tell which QVM in this pair ensemble that you're speaking to. If, however, you were to plug your ears and discard the bitstring that the QVM tried to communicate back to you, then you'd still be unable to tell the difference between which of the two QVMs you're speaking with (since, because you closed your ears, no one managed to accomplish any speaking), and so you really haven't exited the world of density matrices.

So: the recent QVM PR adds support for MEASURE-DISCARD applications (written MEASURE q in Quil, without a classical address) along these lines, and this quilc PR exploits this new simulation support to check the behavior of the compiler on MEASURE instructions by doing an analogue of what it does elsewhere in the tests to check correctness: it calculates a matrix that encodes the behavior (here: several density matrices; elsewhere: a unitary matrix) and checks for equality.

What this has to do with your bug: if this simulation mode were operating well, then the test case is designed to produce one of these ensemble "superpositions", and so you'd expect to see a weighted average of two things. If it were using the measure-and-collapse style of simulation, then you'd see a density matrix with population concentrated in one spot—and that's what you reported.

[1] - This set-up requires that I only MEASURE (and reply) at the very end of the program. If your program is just to MEASURE multiple times in a row, then each run of the pure-state version will reply with the same bitstring as it's repeatedly MEASUREd, but the coin-flipping one might not.

appleby commented 5 years ago

Wow. Thanks for taking the time to write that detailed explanation, and for not leaving out (some of) the finer details :). You managed to keep the conversation at the right abstraction level where I was mostly able to follow along.

One thing I'm still a little confused about. In your point (2), above, you say that density matrices are "suitable for studying combinations of states in a sense somewhat different from ordinary superposition". I think I can see how this would be useful for simulating noise, but are there other places density matrices pop-up?

Also, do I understand correctly that when you perform a MEASURE on one of the two ensemble "superpositions", it will cause both to collapse? Or am I just seeing the collapsed state of the one that "won" the coin toss? If the former, then I'm going to go have a drink to calm my nerves, then circle back! Although I admit I don't really understand how/why wavefunction collapse happens in the "pure state" model, and I just sort of accept it at face value as one of those spooky things that are true about quantum mechanical systems.

The precise mathematical mechanism by which density matrices accomplish this isn't so important. It's more complicated than literally taking formal sums of pure-state things, but I'd advise you to not worry about it until later.

This is advice that I am very happy to accept!

appleby commented 5 years ago

I'm going to run two QVMs simultaneously, and whatever I do to one I'll do to the other, but I'm going to start them from different places, and when I'm finally asked to MEASURE, I'll reply with one of the two measurements that I get by flipping an additional coin and choosing which of the two secret QVM's replies to return based on that

Just realizing that I may have misinterpreted the protocol for the ensemble QVMs. Perhaps what you mean is that MEASUREs are still performed on both, and the coin flip only determines which result I see, not which one gets measured...

ecpeterson commented 5 years ago

That's right: the "ensemble supervisor" performs all operations on both (gates, measurements, everything), and when the user requests a response from the supervisor, the supervisor selects at random from the responses of his subordinates.

I don't myself find this goofy alternative form of superposition to be particularly intuitive / something that arises naturally, but I do find it very practical. There are cool theoretical results from the first perspective:

  1. Suppose that I have some large number of qubits, which I put into my favorite state, and then I hand a subset of them to you to use for your own computations. Depending on what my favorite overall state is, your subset of qubits might behave like a single QVM, initialized into a state somehow deduced from my big state; or, it turns out, your subset might behave like a combination of QVMs, each initialized with different information coming from my big state. (To be concrete, you should think about the three-qubit big state a |000> + b |001> + ... + h |111>, and I'll keep the leftmost qubit secret so that your sub-state then looks like some mixture of a|00> + ... + d|11> and e|00> + ... + h|11>. It could be that a = e, b = f, c = g, and d = h, in which case they behave identically and you might as well have one QVM; or they could be different, and then you sorta have a QVM pair ensemble.)
  2. There's actually a converse result: starting with your favorite ensemble of QVMs, it's possible for me to construct a single pure-state QVM involving twice as many qubits, hand you half of them and keep the other half for myself, and the 'ensemble' that results by the above procedure will have identical behavior to your original favorite ensemble.

These results are conceptually attractive, but they're computationally obnoxious: without any further input, you'd expect simulating these scenarios to require simulating the secret pure state, which can be expensive and which is breaking the abstraction barrier where you're not supposed to need access to my private data.

Meanwhile, the density matrix formalism makes simulation of these scenarios quite attractive: the operation of 'discarding' parts of a quantum system is given by the "partial trace", which is extremely mathematically simple, and the simulation of the resulting ensemble of QVMs can be done by one process in a way that guarantees that no knowledge (much less: total knowledge) is required of any parent quantum system.

At any rate, this partitioning of natural computational resources happens often enough that it's a good perspective to adopt: you could be literally be borrowing someone's qubits; you can think of 'noise' as being a background daemon whose qubits you're borrowing while it continues to run some process on the larger collection; you could swap qubits with someone as a means of communication; you might want to understand when it's safe to release resources, so that you can 'drop' a qubit from consideration without leaving it in some kind of dirty state; ... . Density matrices (or, at least, "open quantum systems") are lurking around the corner of each of these ideas.

appleby commented 5 years ago

This has certainly given me something to chew on! The 3-qubit concrete example was very welcome, and (I think) helped clarify some confusion I had about in what sense these ensembles can be considered a "superposition".

I am still not sure about this "partial trace" business, but I suspect that is heading in the direction of your earlier warning about ignoring the mathematical particulars of density matrices, which I will heed :).