Inspiration
We started tackling the problem by working out algorithms that could work for small cases of the desired state. For instance, much of our inspiration came from initially finding an algorithm that worked for n = 1 and all N. From there, we recognized that Dicke states for larger N could break down into tensor products of smaller-N states, and thus tried to come up with an inductive solution. After looking through some of the existing literature dealing with this, we realized we could use induction not only to break down the desired state but also to create convenient unitaries that made our algorithm both simpler to think about and also implement. Additionally, the constraints of needing to use a ladder implementation scheme on the Google Willow chip guided what kind of algorithm we wanted to make.
What it does
We implemented a modified "divide and conquer" algorithm that prepares an arbitrary Dicke state of length N and weight n. To do so, it first splits the set of N qubits into two halves and produces a weighted sum of states with every "one" qubit in each respective half positioned at the end, given that their Dicke state unitary for k - 1 also produces a Dicke state with weight k - 1. This is the "divided" state. We then inductively construct unitaries that operate on each half in each weighted sum to turn this divided state into the desired Dicke state, the "conquer" step.
The paper proposes different ways of performing the divide algorithm based on the architecture of the quantum computer. A “ladder” structure, where qubits are connected to 4 immediate neighbors in a lattice, and the linear nearest-neighbor architecture, where the qubits are arranged in a line, and operations can only be performed on each qubit's immediate neighbor. In the ladder architecture, the divide step of the algorithm can be made simpler by arranging the first half of the qubits in big endian (ascending) order, and the second half in little endian (descending order). By first putting the first k little endian qubits in state |1>, then rotating the big endian half into a weighted sum from k’ going from 0 to k, of |0^(n/2-k’)1^k’ >, with weights determined by how many of the total (N) Dicke states have k’ 1's in their first half qubits, then using a CNOT gate controlled on qubit i < n/2 acting on qubit (2floor(n/2)-i+1), allowing for much fewer CNOT gates as opposed to the nearest neighbor architecture, which requires either interleaving the qubits as qubit 1,n,2,n-1,... then performing multiple swaps back to (big endian, little endian) or ordering both in reverse, and then performing CNOT’s and swaps.
Beyond constructing the logical circuit, our algorithm maps the circuit onto the physical qubits of the 105-qubit Google Willow processor using a calibration-aware grid selection and embedding algorithm. Because physical qubits and couplers vary in error rates across the chip, choosing where to place the circuit matters as much as the gate count itself. We build a weighted connectivity graph of the Willow grid using the device's calibration data: two-qubit CZ Pauli error rates, single-qubit Pauli error rates, state-dependent readout errors (0 -> 1 and 1 -> 0 weighted by the Dicke state's marginal excitation probability n/N), idle dephasing rates, spectator crosstalk, and shared diagonal readout-line penalties. Next, we extract the exact gate and idle-moment workload of our circuit template so we know how many CZ and single-qubit operations each logical wire and coupler will execute. Using a pruned depth-first search and subgraph matching, our selector evaluates both 2D ladder embeddings (a 2 x k rectangular core with routed tails) and 1D linear chains in both forward and reverse orientations, picking the exact set of physical qubits that minimizes the total expected log-infidelity of the circuit.
How we built it
In our first run through of trying to come up with the algorithm, we tested out different combinations of smaller puzzle pieces that we knew how to work with, like specific combinations of CNOT and SWAP gates, with pen and paper to get a feel for the problem. We then began to finalize the concept for our algorithm, and in the process of coding it up, found places where we could tweak it to make it more efficient and also suit our purposes of implementation. Finally, we iterated through several rounds of coding using Cirq and testing simulations to lower the error rate.
Challenges we ran into
First and foremost, our team joined this challenge with varying levels of experience with the material. We decided to enter the standard track and had to delegate responsibilities accordingly based on each team member's experience.
After breaking down what our problem was, we had to read an extensive amount of literature detailing methods of implementing Dicke States. Interpreting these research articles proved to be a struggle, but ultimately paid off as our algorithm was based on ideas and methods from multiple research papers. Additionally, preparing the theoretical algorithm as code and optimizing it for the Willow chip created an additional challenge, for example, one proposed algorithm required doubly controlled CNOT gates, which is not supported on Willow.
Accomplishments that we're proud of
Even after our logical algorithm worked in noiseless simulation, we had to find new ways of optimizing our fidelity on real, noisy hardware. One of the accomplishments we are most proud of is designing our hardware-aware grid navigation and qubit selection algorithm for the Willow chip. Instead of treating all qubits on the grid as equal or picking an arbitrary path, we built an embedding scorer that pairs the exact structure of our Dicke state circuit with the physical calibration profile of the processor. Because our divide-and-conquer circuit uses qubits asymmetrically, with certain couplers executing far more CZ gates and edge qubits sitting idle for longer stretches, a generic shortest-path search leaves performance on the table. Our algorithm maps the busiest logical couplers onto the lowest-error physical CZ links, assigns long-idling qubits to nodes with lower relaxation and dephasing rates, avoids diagonal readout-line collisions, and dynamically chooses between a 2D ladder layout and a 1D chain based on what the chip's live error rates favor. Building a selector that connects abstract quantum circuit theory to the physical constraints of Google's hardware gave us a major boost in overall score and tied our whole project together.
What we learned
We can definitively say that after working on this project, our knowledge of quantum algorithms and the step-by-step process of how an algorithm is actually thought of, built, and then actually realized on hardware like a Willow chip works. Additionally, we learned about how physical constraints, such as needing to use ladder versus nearest-neighbor architecture or only being able to use specific gates, can guide how a quantum algorithm is built.
What's next for Google QAI: CNOT Employed
We are excited to see other teams' approaches to this problem, and how our thought processes varied. In the future, we also hope to continue learning about resources in the Duke Quantum Center and staying up to date with innovations in the field!
Built With
- cirq
- python
