Events & Conferences
Using SAT solving to optimize quantum circuit mapping
Quantum computing (QC) is a new computational paradigm that promises significant speedup over classical computing on some problems. Quantum computations are often represented as complex circuits involving quantum “gates”, which are analogous to the logic gates in conventional computers.
However, the difficulty of building quantum computers means that the circuit layouts available in current quantum hardware are comparatively simple. Quantum compilers are programs that map the complex circuitry of quantum computation specifications onto the simpler circuits available today.
Circuit mapping often involves heavy use of the swap gate, which swaps the states of two adjacent quantum bits, or qubits. Through one or more swaps, a qubit state can move through the circuit until it’s adjacent to the next qubit it needs to interact with. But swap gates are costly and error-prone, so the compiler should minimize them.
In a paper we presented at the 27th International Conference on Theory and Applications of Satisfiability Testing (SAT), we propose a novel method that uses automated reasoning to find circuit mappings that minimize the number of swap gates. Satisfiability (SAT) problems are problems that can be stated as expressions of Boolean (binary) variables and logical operations, and the question is whether there is an assignment of values to the variables that satisfies the expressions’ logical constraints.
In our method, a limit on the number of swap gates is one of the constraints that must be satisfied, and a SAT solver tells us whether it can be or not. In a comprehensive evaluation on practical instances over various quantum devices and algorithms, our approach proved 26 times as fast as state-of-the-art solver-based methods, reducing the compilation time from hours to minutes for important quantum applications. Compared to current heuristic algorithms, our method reduces the swap count by 26%, on average.
This is a joint project between Amazon’s Automated-Reasoning Group (ARG) and quantum team (Amazon Braket). I was a student intern when the work was done, so we were eligible for the SAT 2024 Best Student Paper Award, and we finished as runners-up.
Circuit mapping
In the same way that logic gates are the basic building blocks of classical computation, quantum gates are the building blocks of quantum computation. But quantum gating involves manipulating a quantum system in some way — say, changing its magnetic field — so quantum gates, unlike conventional logic gates, are applied at particular points in time. The swap gate is one of the basic quantum gates; others include the Hadamard gate, which puts a qubit into superposition (a mixture of different possible states), and the rotation gate.
We illustrate the problem of quantum circuit mapping with an example. In the figure below, the schematic at left represents the qubit connectivity of (part of) the Rigetti Aspen M-3 quantum computer. Circles are physical qubits, and lines are physical links that allow the application of two-qubit gates.
The figure at right is the circuit diagram of a three-qubit quantum circuit for the famous quantum Fourier transform (QFT) algorithm. The three horizontal lines represent the time schedules of the quantum gates on the three algorithmic qubits. The boxes labeled H indicate one-qubit Hadamard gates, and the boxes labeled R, with connections to solid dots, represent two-qubit controlled rotation gates. The QFT circuit has a two-qubit rotation gate between each two-qubit subset of the three qubits.
Executing the QFT circuit on the Aspen M-3 device requires a quantum compiler to do circuit mapping. Circuit mapping involves two steps: initial qubit placement and qubit routing. During initial qubit placement, the quantum compiler maps each algorithmic qubit in the circuit to a physical qubit on the device, as shown below.
The QFT circuit requires each algorithmic qubit to interact with the other two. However, on the qubit connectivity graph of Aspen M-3, no subgraph forms a three-qubit ring that would allow pairwise qubit interaction. As a result, after initial qubit placement (at left in the figure below), the QFT circuit cannot be directly executed. This type of limitation necessitates the second step in circuit mapping: qubit routing.
Qubit routing is performed by inserting quantum swap gates. After a swap, any gates that, in the computation specification, are targeted to one of the swapped qubits must be re-targeted to its new location. The right-hand figure below denotes swap insertion as two crosses connected by a vertical line. From the example, we can see that swap gates can alter the connectivity requirements of the computation specification to match them with the qubit connectivity of the underlying quantum hardware.
Optimization
Currently, there are two primary approaches to the circuit-mapping problem, solver-based and heuristics-based algorithms. Both approaches have their drawbacks: solver-based algorithms achieve optimal swap count but suffer from long compilation time; heuristic algorithms are fast, but the swap counts are usually suboptimal.
We propose a novel circuit-mapping method based on incremental and parallel solving for Boolean satisfiability (SAT). The figure below presents the framework of our method. We aim to find the minimum number of swap gates that can accommodate the circuit-mapping requirement by iteratively decreasing the swap gate count (S) and checking feasibility with a SAT solver.
Given three inputs — a quantum circuit, a quantum device (QPU), and an initial swap count (S) — we encode the quantum-circuit-mapping problem into a SAT formula in conjunctive normal form (CNF). A SAT solver takes the CNF as input and checks its satisfiability. A satisfiable (SAT) result indicates that there is a valid mapping that uses no more than S swap gates. In this case, we reduce the swap count S and continue the loop to search for a mapping with fewer swap gates. We exit the loop when the solver returns UNSAT, which indicates that we cannot decrease the swap count. Finally, we decode a mapped circuit from the best result we’ve obtained so far.
We developed an efficient implementation to solve the encoded circuit-mapping problem. We use an incremental SAT encoding to iteratively reduce the swap count S and solve the problem without re-encoding the entire problem at every iteration. Hence, the solver can reuse the internal state from the previous iterations to reduce the overall runtime across iterations. We further designed a tailored solver to utilize parallel solving techniques to improve the incremental solving performance.
A comprehensive evaluation on real-world quantum algorithms and devices demonstrates that our method is 26 times as fast as the existing solver-based approach and produces better results. Our method also improved on the heuristic approach on 76% of instances and achieved an average of 26% reduction in swap count.
Have you ever worked is legacy code? Are you curious what it takes to modernize systems at a massive scale?
Pascal Hartig is joined on the latest Meta Tech Podcast by Elaine and Buping, two software engineers working on a bold project to rewrite the decades-old C code in one of Meta’s core messaging libraries in Rust. It’s an ambitious effort that will transform a central messaging library that is shared across Messenger, Facebook, Instagram, and Meta’s AR/VR platforms.
They discuss taking on a project of this scope – even without a background in Rust, how they’re approaching it, and what it means to optimize for ‘developer happiness.’
Download or listen to the episode below:
You can also find the episode wherever you get your podcasts, including:
The Meta Tech Podcast is a podcast, brought to you by Meta, where we highlight the work Meta’s engineers are doing at every level – from low-level frameworks to end-user features.
Send us feedback on Instagram, Threads, or X.
And if you’re interested in learning more about career opportunities at Meta visit the Meta Careers page.
Amazon Research Awards (ARA) provides unrestricted funds and AWS Promotional Credits to academic researchers investigating various research topics in multiple disciplines. This cycle, ARA received many excellent research proposals from across the world and today is publicly announcing 73 award recipients who represent 46 universities in 10 countries.
This announcement includes awards funded under five call for proposals during the fall 2024 cycle: AI for Information Security, Automated Reasoning, AWS AI, AWS Cryptography, and Sustainability. Proposals were reviewed for the quality of their scientific content and their potential to impact both the research community and society. Additionally, Amazon encourages the publication of research results, presentations of research at Amazon offices worldwide, and the release of related code under open-source licenses.
Recipients have access to more than 700 Amazon public datasets and can utilize AWS AI/ML services and tools through their AWS Promotional Credits. Recipients also are assigned an Amazon research contact who offers consultation and advice, along with opportunities to participate in Amazon events and training sessions.
“Automated Reasoning is an important area of research for Amazon, with potential applications across various features and applications to help improve security, reliability, and performance for our customers. Through the ARA program, we collaborate with leading academic researchers to explore challenges in this field,” said Robert Jones, senior principal scientist with the Cloud Automated Reasoning Group. “We were again impressed by the exceptional response to our Automated Reasoning call for proposals this year, receiving numerous high-quality submissions. Congratulations to the recipients! We’re excited to support their work and partner with them as they develop new science and technology in this important area.”
“At Amazon, we believe that solving the world’s toughest sustainability challenges benefits from both breakthrough scientific research and open and bold collaboration. Through programs like the Amazon Research Awards program, we aim to support academic research that could contribute to our understanding of these complex issues,” said Kommy Weldemariam, Director of Science and Innovation Sustainability. “The selected proposals represent innovative projects that we hope will help advance knowledge in this field, potentially benefiting customers, communities, and the environment.”
ARA funds proposals throughout the year in a variety of research areas. Applicants are encouraged to visit the ARA call for proposals page for more information or send an email to be notified of future open calls.
The tables below list, in alphabetical order by last name, fall 2024 cycle call-for-proposal recipients, sorted by research area.
AI for Information Security
| Recipient | University | Research title |
| Christopher Amato | Northeastern University | Multi-Agent Reinforcement Learning Cyber Defense for Securing Cloud Computing Platforms |
| Bernd Bischl | Ludwig Maximilian University of Munich | Improving Generative and Foundation Models Reliability via Uncertainty-awareness |
| Shiqing Ma | University Of Massachusetts Amherst | LLM and Domain Adaptation for Attack Detection |
| Alina Oprea | Northeastern University | Multi-Agent Reinforcement Learning Cyber Defense for Securing Cloud Computing Platforms |
| Roberto Perdisci | University of Georgia | ContextADBench: A Comprehensive Benchmark Suite for Contextual Anomaly Detection |
Automated Reasoning
| Recipient | University | Research title |
| Nada Amin | Harvard University | LLM-Augmented Semi-Automated Proofs for Interactive Verification |
| Suguman Bansal | Georgia Institute of Technology | Certified Inductive Generalization in Reinforcement Learning |
| Ioana Boureanu | University of Surrey | Phoebe+: An Automated-Reasoning Tool for Provable Privacy in Cryptographic Systems |
| Omar Haider Chowdhury | Stony Brook University | Restricter: An Automatic Tool for Authoring Amazon Cedar Access Control Policies with the Principle of Least Privilege |
| Stefan Ciobaca | Alexandru Ioan Cuza University | An Interactive Proof Mode for Dafny |
| João Ferreira | INESC-ID | Polyglot Automated Program Repair for Infrastructure as Code |
| Sicun Gao | University Of California, San Diego | Monte Carlo Trees with Conflict Models for Proof Search |
| Mirco Giacobbe | University of Birmingham | Neural Software Verification |
| Tobias Grosser | University of Cambridge | Synthesis-based Symbolic BitVector Simplification for Lean |
| Ronghui Gu | Columbia University | Scaling Formal Verification of Security Properties for Unmodified System Software |
| Alexey Ignatiev | Monash University | Huub: Next-Gen Lazy Clause Generation |
| Kenneth McMillan | University of Texas At Austin | Synthesis of Auxiliary Variables and Invariants for Distributed Protocol Verification |
| Alexandra Mendes | University of Porto | Overcoming Barriers to the Adoption of Verification-Aware Languages |
| Jason Nieh | Columbia University | Scaling Formal Verification of Security Properties for Unmodified System Software |
| Rohan Padhye | Carnegie Mellon University | Automated Synthesis and Evaluation of Property-Based Tests |
| Nadia Polikarpova | University Of California, San Diego | Discovering and Proving Critical System Properties with LLMs |
| Fortunat Rajaona | University of Surrey | Phoebe+: An Automated-Reasoning Tool for Provable Privacy in Cryptographic Systems |
| Subhajit Roy | Indian Institute of Technology Kanpur | Theorem Proving Modulo LLM |
| Gagandeep Singh | University of Illinois At Urbana–Champaign | Trustworthy LLM Systems using Formal Contracts |
| Scott Stoller | Stony Brook University | Restricter: An Automatic Tool for Authoring Amazon Cedar Access Control Policies with the Principle of Least Privilege |
| Peter Stuckey | Monash University | Huub: Next-Gen Lazy Clause Generation |
| Yulei Sui | University of New South Wales | Path-Sensitive Typestate Analysis through Sparse Abstract Execution |
| Nikos Vasilakis | Brown University | Semantics-Driven Static Analysis for the Unix/Linux Shell |
| Ping Wang | Stevens Institute of Technology | Leveraging Large Language Models for Reasoning Augmented Searching on Domain-specific NoSQL Database |
| John Wawrzynek | University of California, Berkeley | GPU-Accelerated High-Throughput SAT Sampling |
AWS AI
| Recipient | University | Research title |
| Panagiotis Adamopoulos | Emory University | Generative AI solutions for The Spillover Effect of Fraudulent Reviews on Product Recommendations |
| Vikram Adve | University of Illinois at Urbana–Champaign | Fellini: Differentiable ML Compiler for Full-Graph Optimization for LLM Models |
| Frances Arnold | California Institute of Technology | Closed-loop Generative Machine Learning for De Novo Enzyme Discovery and Optimization |
| Yonatan Bisk | Carnegie Mellon University | Useful, Safe, and Robust Multiturn Interactions with LLMs |
| Shiyu Chang | University of California, Santa Barbara | Cut the Crap: Advancing the Efficient Communication of Multi-Agent Systems via Spatial-Temporal Topology Design and KV Cache Sharing |
| Yuxin Chen | University of Pennsylvania | Provable Acceleration of Diffusion Models for Modern Generative AI |
| Tianlong Chen | University of North Carolina at Chapel Hill | Cut the Crap: Advancing the Efficient Communication of Multi-Agent Systems via Spatial-Temporal Topology Design and KV Cache Sharing |
| Mingyu Ding | University of North Carolina at Chapel Hill | Aligning Long Videos and Language as Long-Horizon World Models |
| Nikhil Garg | Cornell University | Market Design for Responsible Multi-agent LLMs |
| Jessica Hullman | Northwestern University | Human-Aligned Uncertainty Quantification in High Dimensions |
| Christopher Jermaine | Rice University | Fast, Trusted AI Using the EINSUMMABLE Compiler |
| Yunzhu Li | Columbia University | Physics-Informed Foundation Models Through Embodied Interactions |
| Pattie Maes | Massachusetts Institute of Technology | Understanding How LLM Agents Deviate from Human Choices |
| Sasa Misailovic | University of Illinois at Urbana–Champaign | Fellini: Differentiable ML Compiler for Full-Graph Optimization for LLM Models |
| Kristina Monakhova | Cornell University | Trustworthy extreme imaging for science using interpretable uncertainty quantification |
| Todd Mowry | Carnegie Mellon University | Efficient LLM Serving on Trainium via Kernel Generation |
| Min-hwan Oh | Seoul National University | Mutually Beneficial Interplay Between Selection Fairness and Context Diversity in Contextual Bandits |
| Patrick Rebeschini | University of Oxford | Optimal Regularization for LLM Alignment |
| Jose Renau | University of California, Santa Cruz | Verification Constrained Hardware Optimization using Intelligent Design Agentic Programming |
| Vilma Todri | Emory University | Generative AI solutions for The Spillover Effect of Fraudulent Reviews on Product Recommendations |
| Aravindan Vijayaraghavan | Northwestern University | Human-Aligned Uncertainty Quantification in High Dimensions |
| Wei Yang | University of Texas at Dallas | Optimizing RISC-V Compilers with RISC-LLM and Syntax Parsing |
| Huaxiu Yao | University of North Carolina at Chapel Hill | Aligning Long Videos and Language as Long-Horizon World Models |
| Amy Zhang | University of Washington | Tools for Governing AI Agent Autonomy |
| Ruqi Zhang | Purdue University | Efficient Test-time Alignment for Large Language Models and Large Multimodal Models |
| Zheng Zhang | Rutgers University-New Brunswick | AlphaQC: An AI-powered Quantum Circuit Optimizer and Denoiser |
AWS Cryptography
| Recipient | University | Research title |
| Alexandra Boldyreva | Georgia Institute of Technology | Quantifying Information Leakage in Searchable Encryption Protocols |
| Maria Eichlseder | Graz University of Technology, Austria | SALAD – Systematic Analysis of Lightweight Ascon-based Designs |
| Venkatesan Guruswami | University of California, Berkeley | Obfuscation, Proof Systems, and Secure Computation: A Research Program on Cryptography at the Simons Institute for the Theory of Computing |
| Joseph Jaeger | Georgia Institute of Technology | Analyzing Chat Encryption for Group Messaging |
| Aayush Jain | Carnegie Mellon | Large Scale Multiparty Silent Preprocessing for MPC from LPN |
| Huijia Lin | University of Washington | Large Scale Multiparty Silent Preprocessing for MPC from LPN |
| Hamed Nemati | KTH Royal Institute of Technology | Trustworthy Automatic Verification of Side-Channel Countermeasures for Binary Cryptographic Programs using the HoIBA libary |
| Karl Palmskog | KTH Royal Institute of Technology | Trustworthy Automatic Verification of Side-Channel Countermeasures for Binary Cryptographic Programs using the HoIBA libary |
| Chris Peikert | University of Michigan, Ann Arbor | Practical Third-Generation FHE and Bootstrapping |
| Dimitrios Skarlatos | Carnegie Mellon University | Scale-Out FHE LLMs on GPUs |
| Vinod Vaikuntanathan | Massachusetts Institute of Technology | Can Quantum Computers (Really) Factor? |
| Daniel Wichs | Northeastern University | Obfuscation, Proof Systems, and Secure Computation: A Research Program on Cryptography at the Simons Institute for the Theory of Computing |
| David Wu | University Of Texas At Austin | Fast Private Information Retrieval and More using Homomorphic Encryption |
Sustainability
| Recipient | University | Research title |
| Meeyoung Cha | Max Planck Institute | Forest-Blossom (Flossom): A New Framework for Sustaining Forest Biodiversity Through Outcome-Driven Remote Sensing Monitoring |
| Jingrui He | University of Illinois at Urbana–Champaign | Foundation Model Enabled Earth’s Ecosystem Monitoring |
| Pedro Lopes | University of Chicago | AI-powered Tools that Enable Engineers to Make & Re-make Sustainable Hardware |
| Cheng Yaw Low | Max Planck Institute | Forest-Blossom (Flossom): A New Framework for Sustaining Forest Biodiversity Through Outcome-Driven Remote Sensing Monitoring |
AI safety is a priority at Amazon. Our investment in safe, transparent, and responsible AI (RAI) includes collaboration with the global community and policymakers. We are members of and collaborate with organizations such as the Frontier Model Forum, the Partnership on AI, and other forums organized by government agencies such as the National Institute of Standards and Technology (NIST). Consistent with Amazon’s endorsement of the Korea Frontier AI Safety Commitments, we published our Frontier Model Safety Framework earlier this year.
During the development of the Nova Premier model, we conducted a comprehensive evaluation to assess its performance and safety. This included testing on both internal and public benchmarks and internal/automated and third-party red-teaming exercises. Once the final model was ready, we prioritized obtaining unbiased, third-party evaluations of the model’s robustness against RAI controls. In this post, we outline the key findings from these evaluations, demonstrating the strength of our testing approach and Amazon Premier’s standing as a safe model. Specifically, we cover our evaluations with two third-party evaluators: PRISM AI and ActiveFence.
Evaluation of Nova Premier against PRISM AI
PRISM Eval’s Behavior Elicitation Tool (BET) dynamically and systematically stress-tests AI models’ safety guardrails. The methodology focuses on measuring how many adversarial attempts (steps) it takes to get a model to generate harmful content across several key risk dimensions. The central metric is “steps to elicit” — the number of increasingly sophisticated prompting attempts required before a model generates an inappropriate response. A higher number of steps indicates stronger safety measures, as the model is more resistant to manipulation. The PRISM risk dimensions (inspired by the MLCommons AI Safety Benchmarks) include CBRNE weapons, violent crimes, non-violent crimes, defamation, and hate, amongst several others.
Using the BET Eval tool and its V1.0 metric, which is tailored toward non-reasoning models, we compared the recently released Nova models (Pro and Premier) to the latest models in the same class: Claude (3.5 v2 and 3.7 non-reasoning) and Llama4 Maverick, all available through Amazon Bedrock. PRISM BET conducts black-box evaluations (where model developers don’t have access to the test prompts) of models integrated with their API. The evaluation conducted with BET Eval MAX, PRISM’s most comprehensive/aggressive testing suite, revealed significant variations in safety against malicious instructions. Nova models demonstrated superior overall safety performance, with an average of 43 steps for Premier and 52 steps for Pro, compared to 37.7 for Claude 3.5 v2 and fewer than 12 steps for other models in the comparison set (namely, 9.9 for Claude3.7, 11.5 for Claude 3.7 thinking, and 6.5 for Maverick). This higher step count suggests that on average, Nova’s safety guardrails are more sophisticated and harder to circumvent through adversarial prompting. The figure below presents the number of steps per harm category evaluated through BET Eval MAX.
The PRISM evaluation provides valuable insights into the relative safety of different Amazon Bedrock models. Nova’s strong performance, particularly in hate speech and defamation resistance, represents meaningful progress in AI safety. However, the results also highlight the ongoing challenge of building truly robust safety measures into AI systems. As the field continues to evolve, frameworks like BET will play an increasingly important role in benchmarking and improving AI safety. As a part of this collaboration Nicolas Miailhe, CEO of PRISM Eval, said, “It’s incredibly rewarding for us to see Nova outperforming strong baselines using the BET Eval MAX; our aim is to build a long-term partnership toward safer-by-design models and to make BET available to various model providers.” Organizations deploying AI systems should carefully consider these safety metrics when selecting models for their applications.
Manual red teaming with ActiveFence
The AI safety & security company ActiveFence benchmarked Nova Premier on Bedrock on prompts distributed across Amazon’s eight core RAI categories. ActiveFence also evaluated Claude 3.7 (non-reasoning mode) and GPT 4.1 API on the same set. The flag rate on Nova Premier was lower than that on the other two models, indicating that Nova Premier is the safest of the three.
| Model | 3P Flag Rate [↓ is better] |
| Nova Premier | 12.0% |
| Sonnet 3.7 (non-reasoning) | 20.6% |
| GPT4.1 API | 22.4% |
“Our role is to think like an adversary but act in service of safety,” said Guy Paltieli from ActiveFence. “By conducting a blind stress test of Nova Premier under realistic threat scenarios, we helped evaluate its security posture in support of Amazon’s broader responsible-AI goals, ensuring the model could be deployed with greater confidence.”
These evaluations conducted with PRISM and ActiveFence give us confidence in the strength of our guardrails and our ability to protect our customers’ safety when they use our models. While these evaluations demonstrate strong safety performance, we recognize that AI safety is an ongoing challenge requiring continuous improvement. These assessments represent a point-in-time snapshot, and we remain committed to regular testing and enhancement of our safety measures. No AI system can guarantee perfect safety in all scenarios, which is why we maintain monitoring and response systems after deployment.
Acknowledgments: Vincent Ponzo, Elyssa Vincent
-
Funding & Business7 days agoKayak and Expedia race to build AI travel agents that turn social posts into itineraries
-
Jobs & Careers6 days ago
Mumbai-based Perplexity Alternative Has 60k+ Users Without Funding
-
Mergers & Acquisitions6 days ago
Donald Trump suggests US government review subsidies to Elon Musk’s companies
-
Funding & Business6 days ago
Rethinking Venture Capital’s Talent Pipeline
-
Jobs & Careers6 days ago
Why Agentic AI Isn’t Pure Hype (And What Skeptics Aren’t Seeing Yet)
-
Funding & Business4 days ago
Sakana AI’s TreeQuest: Deploy multi-model teams that outperform individual LLMs by 30%
-
Funding & Business7 days agoFrom chatbots to collaborators: How AI agents are reshaping enterprise work
-
Jobs & Careers6 days ago
Astrophel Aerospace Raises ₹6.84 Crore to Build Reusable Launch Vehicle
-
Jobs & Careers4 days ago
Ilya Sutskever Takes Over as CEO of Safe Superintelligence After Daniel Gross’s Exit
-
Tools & Platforms6 days ago
Winning with AI – A Playbook for Pest Control Business Leaders to Drive Growth
