Scientific boffin - skip my narrative and read the paper here.
For the rest of us…
In yet another month of grand claims from quantum companies, it seems this small yet humble nugget from researchers Élie Gouzien and Nicolas Sangouard at Alice & Bob may have been overlooked, under-celebrated, and underestimated.
My Dad Was A Wood Elf
My late father was a great woodworker.
I swear he was half wood elf.
If you gave him some bits of wood, he’d tinker around in his garage and out would roll a table or a chest of drawers.
There was nothing the guy couldn’t seemingly build using timber.
I asked him once, “How do you know if someone is really good with carpentry?”
His answer was simple: great carpenters don’t leave much waste behind.
They cut exact dimensions using just the amount of wood required-minimal offcuts, barely any scrap in the “bits pile,” and only the faintest whisper of sawdust on the floor.
Now, replace “wood” with quantum gates, and you’ve got the problem researchers are trying to solve in quantum computing: building circuits with perfect precision using the smallest possible number of steps.
Why this is relevant to quantum computing is that these two researchers from Alice & Bob created a method for generating computational circuits in the most effective way possible-the fewest cuts of wood, the most elegant use of the material.
Welcome to the world of optimal gate synthesis.
What’s the Big Deal?
Quantum computers are finicky beasts.
They’re not just hard to build-they’re expensive, power-hungry, and sensitive enough that a scientist’s sneeze might throw off an entire computation.
So when it comes to programming them, every single quantum gate (i.e., instruction) matters.
If you waste one, it’s like trying to win race from the traffic lights turning green with the handbrake half-on.
This paper tackles one simple but vital question:
How do we build a quantum circuit that does exactly what we want-using only a specific set of allowed gates-and using the fewest gates possible?
How They Did It
Here’s the clever bit.
Instead of hacking away at the problem by hand (like most current compilers do), the authors turned the whole thing into a puzzle for a computer to solve.
If you’ve been in computing since the dawn of time, you’ll be familiar with SAT solvers.
For the newbies:
SAT solvers have been linked to automated theorem proving and formal verification since the 1960s.
In 1960, Martin Davis and Hilary Putnam introduced a resolution-based procedure for propositional logic-the Davis–Putnam algorithm.
In 1962, it evolved into the Davis–Putnam–Logemann–Loveland (DPLL) algorithm, the foundation of modern SAT solvers.
What does a SAT Solver Do ?
SAT stands for “satisfiability”-specifically, the Boolean Satisfiability Problem.
Can I assign true or false (yes or no) to a bunch of variables so that a whole bunch of logical statements all work out to be true?
It’s like being handed a long list of conditions and needing to figure out if there’s any combination of yes/no switches that makes everything click into place.
🔦 The Light Switch Riddle
Imagine this:
- The kitchen light must be ON if the bathroom light is OFF.
- The bathroom light must be OFF if the bedroom light is ON.
- The bedroom light must be ON if the kitchen light is OFF.
Now your job is to figure out:
Can I turn these lights ON or OFF so all these conditions are true at the same time?
A SAT solver does exactly that-but at quantum scale, with millions of logical switches and constraints.
If a solution exists, it finds it. If not, it proves it can’t be done.
And that is (in a simplified way) what the researchers at Alice and Bob have done.
Specifically, they:
- Translated the quantum gate synthesis problem into a SAT (satisfiability) problem – this is a fancy way of saying: “Can you set these digital light switches (true/false variables) so a complex condition is true?”
- Used Boolean logic (i.e., maths with only “yes” or “no”) to represent whether certain gates are used and how they combine.
- Fed this puzzle into SAT solvers-turbocharged logic solvers used in everything from microchip design to Sudoku-solving AIs.
- Repeated the process until they found the shortest solution-or proved there isn’t one with fewer gates.
It’s like asking an AI super carpenter,
“Can I make this oak cabinet with these six planks of wood?”
And it either spits out the plans for your cabinet tor tells you politely:
“Not with six, mate- you need eight.”
Why It’s Hard (And Brilliant)
Most quantum compilers guess, fiddle, and hope for the best.
These researchers, instead, guarantee:
“This is the best you can do.”
That’s huge.
Shaving even a few gates off a tiny subroutine saves resources down the line.
It’s like saving a cup of petrol per trip-multiplied across a fleet of a billion cars.
The Issues?
It’s computationally expensive-like planning every possible chess move in advance.
Not practical for big circuits.
But for tiny, repeated building blocks? Perfect.
Imagine you’re a carpenter tasked with building a perfect oak bookshelf:
- You can only use a small selection of tools from your shed.
- Every plank must be cut and joined exactly right.
- And you want to use as few tools and steps as possible- because time is money, and you’ve got a cup of tea brewing.
Here’s how the paper helps our carpenter build the shelf, the quantum way:
🔧 SAT Encoding – Turning Carpentry into a Yes/No Toolbox
You’ve got a big chart that says:
“Should I use the saw here? Yes or no?” “Should I drill this hole now? Yes or no?” “Is the chisel needed at step 3?”
Every possible combination of yes/no answers is like a different way of building the shelf.
A SAT solver is like your apprentice who runs through every possible combination of tools and steps, super fast, and figures out:
- Which sequence builds the perfect bookshelf, or
- That no combination from your current tools can get the job done.
It’s like solving a puzzle where every tool, each cut of wood, must click into place perfectly, or the shelf wobbles, crashes and falls and your nan’s ashes end up worked into the carpet.
Why It Matters for Business & Tech
- More efficient circuits = Fewer qubits, Less cooling, Lower costs, Faster execution
- Cheaper and greener quantum cloud computing
- Better fault-tolerant systems = More commercial viability
Think of it like software that runs twice as fast and uses half the battery-now apply that to quantum #banking or AI #chemistry simulations.
🚪 Do We Have Wood?
Quantum computing is already tough.
But this new approach lets us tick a key box:
“Built the shortest quantum circuit… provably.”
It won’t replace Google’s full quantum stack tomorrow, but for those fiddly sub-circuits that pop up like dad jokes-it just got easier.
Better design = More efficient quantum circuits = Faster, more powerful quantum compute.
A Scalability Reality Check
This method doesn’t scale well.
As you add qubits, the complexity explodes-like trying to build 1,000 unique bookshelves with hand tools only.
Soon you’re spending more time planning the cuts than making them.
It becomes a notebook-filling, sawdust-stirring, 100-year mission.
Also, its reliance on exact decomposition limits flexibility in noisy, real-world environments.
You could argue that heuristic-based compilers give “good enough” results faster-especially at scale.
But that’s not the point.
Innovation starts with small, precise steps.
This work offers a new lens through which to build smarter, cleaner circuits.
It is like having smarter more efficient lego pieces, being able to use the one block deep, four blocks wide piece exactly where you need it and that elegance in design is critically important when building complex systems.
For small building blocks, it has the potential to make a big difference, no headline grabbing title - but at least as important as the next big “Breakthrough to a zillion QuBits” article to hit your feed.
How they are applied needs to unfold, but for small circuits, quantum at the edge, and other applications they may turn out to be that perfect small bit of wood you need in the wood pile.
Why It’s Contextually Important for Alice & Bob
Alice & Bob, is a Paris-based quantum platform firm, is focused on fault-tolerant quantum computing-they are building the Rolls-Royce of quantum machines. (along with a few others in the same race).
They build systems using limited gate sets, expensive error correction, and ultra-sensitive hardware.
Why This Paper Helps:
- Efficiency = Survival: Fewer gates mean fewer qubits, less power, and lower error correction overhead.
- Small Circuits, Big Impact: Repeated micro-optimisations = Massive cumulative savings.
- Benchmarking: This gives them a provable gold standard to measure their compiler tools against.
- Future Tools: This can be baked into hybrid compiler stacks for small circuit optimisation.
It’s like giving your team of quantum carpenters the most efficient joinery blueprint possible-saving wood, time, and money in an era where every plank (or qubit) is precious.
And thats why it needs to be recognised.
SAT Solvers have been around for a while, it takes a step of considered thinking to apply them to Quantum gate design.
Whoever came up with the idea at Alice and Bob, they shouldn’t have to make the tea.
At least for a while.
Although I believe the team at QAI.AI Analog Physics Inc. started using Sat Solvers in Quantum gate design a few years ago in software, Alice and Bob seem to be the first platform company to drink the Sat Solving cool aid.
