Tag: Vasileios Klimis

The Alien Cookbook

An alien looking on distraught that two bowls of soup are different, one purple, one green.
Image by CS4FN from original soup bowls by OpenClipart-Vectors and alien image by Clker-Free-Vector-Images from Pixabay

How to spot a bad chef when you’ve never tasted the food (OR How to spot a bad quantum simulator when you do not know what the quantum circuit it is simulating is supposed to do.)

Imagine you’re a judge on a wild cooking competition. The contestants are two of the best chefs in the world, Chef Qiskit and Chef Cirq. Today’s challenge is a strange one. You hand them both a mysterious, ancient cookbook found in a crashed spaceship. The recipe you’ve chosen is called “Glorp Soup”. The instructions are very precise and scientific: “… Heat pan to 451 degrees. Stir counter-clockwise for exactly 18.7 seconds. … Add exactly 3 grams of powdered meteorite (with the specified composition). …” The recipe is a perfectly clear algorithm, but since no human has ever made Glorp Soup, nobody knows what it’s supposed to taste, look, or smell like. Both chefs go to their identical kitchens with the exact same alien ingredients. After an hour, they present their dishes.

  • Chef Qiskit brings out a bowl of thick, bubbling, bright purple soup that smells like cinnamon.
  • Chef Cirq brings out a bowl of thin, clear, green soup that smells like lemons.

Now you have a fascinating situation. You have no idea which one is the “real” Glorp Soup. Maybe it’s supposed to be purple, or maybe it’s green. But you have just learned something incredibly important: at least one of your expert chefs made a mistake. They were given the exact same, precise recipe, but they produced two completely different results. You’ve found a flaw in one of their processes without ever knowing the correct answer.

This powerful idea is called Differential Testing.

Cooking with Quantum Rules

In our research, the “alien recipes” we use are called quantum circuits. These are the step-by-step instructions for a quantum computer. And the “chefs” are incredibly complex computer programs called quantum simulators, built by places like Google and IBM.

Scientists give these simulators a recipe (a circuit) to predict what a real quantum computer will cook up. These “dishes” could be the design for a new medicine or a new type of battery. If the simulator-chef gets the recipe wrong, the final result could be useless or even dangerous. But how do you check a chef’s work when the recipe is for a food you’ve never tasted? How do you test a quantum simulator when you do not know exactly what a quantum circuit should do.

FuzzQ: The Robot Quantum Food Critic

We can’t just try one recipe, one quantum circuit. We need to try thousands. So we built a robot “quantum food critic”, a program we call FuzzQ. FuzzQ’s job is to invent new “alien recipes” ie quantum circuits and see if the two “chefs” cook the same dish (i.e. different simulators do the same thing when simulating it). This process of trying out thousands of different, and sometimes very weird, recipes is called Fuzzing.

Here’s how our quantum circuit food critic works:

  1. It writes a recipe: FuzzQ uses a rulebook for “alien cooking” to invent a new, unique, and often very strange quantum circuit.
  2. It gives the recipe to both chefs: It sends the exact same quantum circuit to “Chef Qiskit” (the Qiskit simulator) and “Chef Cirq” (the Cirq simulator).
  3. It tastes the soup: FuzzQ looks at the final result from both. If they’re identical, it assumes they’re correct. But if they do different things, so one did the equivalent of make a purple, bubbling soup and the other made the equivalent of a clear, green soup, FuzzQ sounds the alarm. It has found a bug!

We had FuzzQ invent and “taste-test”, so check the results of, over 800,000 different quantum recipes.

The Tale of the Two Ovens 

Our robot critic found 8 major types of quantum “cooking” errors. One of the most interesting was for a simple instruction called a “SWAP”, which was discovered by looking at how the two chefs used their high-tech “ovens”.

Imagine both chefs have an identical oven with two compartments, a Top Oven and a Bottom Oven. They preheat them according to the recipe: the Top Oven to a very hot 250°C, and the Bottom Oven to a low 100°C. The recipe then has a smart-oven command:

 “Logically SWAP the Top Oven and Bottom Oven.”

Both chefs press the button to do the “SWAP”.

  • Chef Cirq’s oven works as expected. It starts the long process of cooling the top oven and heating the bottom one.
  • Chef Qiskit’s oven, however, is a “smarter” model. It takes a shortcut. It doesn’t change the temperatures at all but just swaps the labels on its digital display so that the one at the top previously labelled the Top Oven is now labelled as the Bottom Oven, and vice versa. The screen now lies, showing Top Oven: 100°C and Bottom Oven: 250°C, even though the physical reality is the opposite: the one at the top is still the incredibly hot, 250°C and the one below it is still 100°C.

The final instruction is: 

“Place the delicate soufflé into the physical TOP OVEN.”

  • Chef Cirq opens his top oven (ie the one positioned above the other and labelled Top Oven), which is now correctly at 100°C, having cooled down, and bakes a perfect soufflé.
  • Chef Qiskit, trusting his display, opens his top oven (ie the one positioned above the other but internally now labelled Bottom Oven) and puts his soufflé inside. But that physical oven that is at the top is still at 250°C. A few minutes later, he has a burnt, smoky crisp.

Our robot judge, FuzzQ, doesn’t need to know how to bake. It just looks at the two final soufflés. One is perfect, and the other is charcoal. The results are different, so FuzzQ sounds the alarm: “Disagreement found!”

This is how we found the bug. We didn’t need to know the “correct temperature”. We only needed to see that the two expert simulators, when given the same instructions, produced two wildly different outcomes. Knowing something now is amiss, further investigation of what each quantum simulator did with those identical instructions, can determine what actually went wrong and the problematic quantum simulator improved. By finding these disagreements, we’re helping to make sure the amazing tools of quantum science are trustworthy.

Vasileios Klimis, Queen Mary University of London

More on …

Getting Technical …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Transitional Automaton: a poem

Image by Агзам Гайсин from Pixabay M

My poetry collection, «Αλγόριθμοι Σιωπής» (Algorithms of Silence), explores the quiet, often unseen structures that shape our inner lives. As a computer scientist and a poet, I’m fascinated by the language we use to describe these systems – whether they are emotional, social, or computational. 

The following piece is an experiment that embodies this theme. It presents a single core idea – about choice, memory, and predetermination – in three different languages: the original Greek poem “Αυτόματον Μεταβατικόν,” an English transcreation, and a pseudocode version that translates the poem’s philosophical questions into the logic of an automaton.

– Vasileios Klimis, Queen Mary University of London

Transitional Automaton

Once,
a decision – small,
like a flaw in a cogwheel –
tilted the whole system toward a version
never written.

In the workshop of habits,
every choice left behind
a trace of activation;
you don’t see it,
but it returns
like a pulse
through a one-way gate.

•

I walk through a matrix of transitions
where each state defines the memory of the next.
Not infinite possibilities –
only those the structure permits.

Is this freedom?
Or merely the optimal illusion
of a system with elastic rules?

•

In moments of quiet
(but not of silence)
I feel the null persisting
not as absence,
but as a repository in waiting.
Perhaps that is where it resides,
all that was never activated.

•

If there is a continuation,
it will resemble a debug session
more than a crisis.

Not a moral crisis;
a recursion.
Who passes down to the final terminal
the most probable path?

•

The question is not
what we lived.
But which of the contingencies
remained active
when we
stopped calculating.

Αυτόματον μεταβατικόν

Κάποτε,
μια απόφαση – μικρή, σαν στρέβλωση σε οδοντωτό τροχό –
έγερνε το σύνολο προς μια εκδοχή
που δεν γράφτηκε ποτέ.

•

Στο εργαστήριο των συνηθειών
κάθε επιλογή άφηνε πίσω της
ένα ίχνος ενεργοποίησης·
δεν το βλέπεις,
αλλά επιστρέφει
σαν παλμός σε μη αντιστρεπτή πύλη.

•

Περπατώ μέσα σ’ έναν πίνακα μεταβάσεων
όπου κάθε κατάσταση ορίζει τη μνήμη της επόμενης.
Όχι άπειρες πιθανότητες –
μόνον όσες η δομή επιτρέπει.
Είναι ελευθερία αυτό;
Ή απλώς η βέλτιστη πλάνη
ενός συστήματος με ελαστικούς κανόνες;

•

Σε στιγμές σιγής (αλλά όχι σιωπής)
νιώθω το μηδέν να επιμένει
όχι ως απουσία,
αλλά ως αποθήκη αναμονής.
Ίσως εκεί διαμένει
ό,τι δεν ενεργοποιήθηκε.

•

Αν υπάρξει συνέχεια,
θα μοιάζει περισσότερο με debug session
παρά με κρίση.

•

Όχι κρίση ηθική·
μία αναδρομή.
Ποιος μεταβιβάζει στο τερματικό του τέλους
το πιο πιθανό μονοπάτι;

•

Η ερώτηση δεν είναι τι ζήσαμε.
Αλλά ποιο από τα ενδεχόμενα έμεινε ενεργό
όταν εμείς
σταματήσαμε να υπολογίζουμε.

Pseudocode Poem version

Pseudocode poems are poems written in pseudocode: the semi-formailsed language used for writing algorithms and planning the design of program. Here is the above poem as a pseudocode poem.

FUNCTION life_automaton(initial_state)
  DEFINE State_Transitions AS Matrix;
  DEFINE active_path AS Log;
  DEFINE potential_paths AS Set = {all_versions_never_written};

  current_state = initial_state;
  system.log("Initializing in the workshop of habits.");

  REPEAT

    WAIT FOR event.decision;
    // a decision — small, like a flaw in a cogwheel
    IF (event.decision.is_subtle) THEN
       previous_state = current_state;
       current_state = State_Transitions.calculate_next
                                (previous_state, event.decision);
       // it returns like a pulse through a one-way gate
       active_path.append(previous_state -> current_state);
       potential_paths.remove(current_state.version);
    END IF

   // Is this freedom? Or merely the optimal illusion
   // of a system with elastic rules?
   
   IF (system.isQuiet) THEN
       // I feel the null persisting
       // not as absence, but as a repository in waiting.
       // Perhaps that is where it resides, all that was never activated.
       PROCESS potential_paths.contemplate();
   END IF

  UNTIL system.isTerminated;
   
  // If there is a continuation,
  // it will resemble a debug session more than a crisis.
  // Not a moral crisis; a recursion.
  DEBUG_SESSION.run(active_path);

  // The question is not what we lived.
  // But which of the contingencies remained active
  // when we stopped calculating.
  RETURN final_state = active_path.getLast();
END FUNCTION

More on

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Shouting at Memory: Where Did My Write Go?

Bat sending out sound waves
Image by 13smok from Pixabay modified by CS4FN

How can computer scientists improve computer memory, ensuring saving things is more secure? If Vasileios Klimis of Queen Mary, University of London’s Theory research group has his way, they will be learning from bats.

Imagine spending hours building the perfect fortress in Minecraft, complete with lava moats and secret passages; or maybe you’re playing Halo, and you’ve just customised your SPARTAN with an epic new helmet. You press ‘Save’, and breathe a sigh of relief. But what happens next? Where does your digital castle or new helmet go to stay safe?

It turns out that when a computer saves something, it’s not as simple as putting a book on a shelf. The computer has lots of different places to put information, and some are much safer than others. Bats are helping us do it better!

The Bat in the Cave

Imagine you’re a bat flying around in a giant, dark cave. You can’t see, so how do you know where the walls are? You let out a loud shout!

SQUEAK!

A moment later, you hear the echo of your squeak bounce back to you. If the echo comes back really, really fast, you know the wall is very close. If it takes a little longer, you know the wall is further away. By listening to the timing of your echoes, you can build a map of the entire cave in your head without ever seeing it. This is called echolocation.

It turns out we can use this exact same idea to “see” inside a computer’s memory!

Fast Desks and Safe Vaults

A computer’s memory is a bit like a giant workshop with different storage areas.

  • There’s a Super-Fast Desk right next to the computer’s brain (the CPU). This is where it keeps information it needs right now. It’s incredibly fast to grab things from this desk, but there’s a catch: if the power goes out, everything on the desk is instantly wiped away and forgotten! If your data is here, it is not safe!
  • Further away, there’s a Big, Safe Vault. It takes a little longer to walk to the vault to store or retrieve things. But anything you put in the vault is safe, even if the power goes out. When you turn the computer back on, the information is still there.

When you press ‘Save’ in your game, you want your information to go from the fast-but-forgetful desk to the slower-but-safe vault. But how can we be sure it got there? We can’t just open up the computer and look!

Shouting and Listening for Echoes

This is where we use our bat’s trick. To check where a piece of information is, a computer scientist can tell the computer to do two things very quickly:

  1. SHOUT! First, it “shouts” by writing a piece of information, like your game score.
  2. LISTEN! Immediately after, it tries to read that same piece of information back. This is like listening for the “echo”.

If the echo comes back almost instantly, we know the information is still on the Super-Fast Desk nearby. But if the echo takes a little longer, it means the information had to travel all the way to the Big, Safe Vault and back!

By measuring the time of that echo, computer scientists can tell exactly where the write went. We can confirm that when you pressed ‘Save’, your information really did make it to the safe place.

The Real Names

In computer science, we have official names for these ideas:

  • The Super-Fast Desk is called the Cache.
  • The Big, Safe Vault is called Non-Volatile Memory (or NVM for short), which is a fancy way of saying it doesn’t forget when the power is off.
  • The whole system of close and far away memory is the Memory Hierarchy.
  • And this cool trick of shouting and listening is what we call Memory Echolocation.

So next time you save a game, you can imagine the computer shouting a tiny piece of information into its own secret cave and listening carefully for the echo to make sure your progress is safe and sound.

– Vasileios Klimis, Queen Mary University of London

More on …

Getting Technical …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos