Quantum Search and Euchre

2025 — the International Year of Quantum !!

In the 100th anniversary of the birth of quantum mechanics, Unesco has officially declared 2025 as the International Year of Quantum Science and Technology.

Quantum mechanics has been a bit of a disruption in the path of scientific discovery, challenging existing fundamental laws of the universe, while also supporting proven behaviours of technologies like lasers, MRI machines, and even semiconductors,

Despite being 100 years old, quantum mechanics is still very very young and this celebration isn’t about looking back on the past century, it is more about the excitement for the future. From quantum solutions for problems once considered impossible, to uncrackable secure communications, and more, this quantum anniversary is really the beginning of a technological revolution.

Quantum and Card Games

In the spirit of 2025’s celebration of quantum, let’s explore a fun intersection of quantum algorithms and card games. Specifically, how Grover’s algorithm, a quantum search method can be applied to find high-value winning hands in a classic card game.

Imagine using quantum principles to search through thousands of possible card combinations to pinpoint the winning ones. While this might appear to be just a theoretical exercise, it is a simple and clear demonstration of quantum algorithm’s potential to solve complex problems more efficiently than classical computers.

In a previous article, I explored how symbolic logic can solve classic puzzles like Einstein’s Zebra Riddle. That solution involved a constraint solver to reason through possibilities and zero in on the only valid solution. This time we take the constraints in card game rules and apply them within a quantum algorithm.

The Oracle, Card hands, Library books…

One of the key components of this quantum method is the "oracle”: a function that identifies true/false conditions.

We can think of the oracle as a sifter on a large set of all possible card hands which will uncover high-value hands. The oracle doesn’t reveal the sifting rules, it is a black-box containing the high-value hand conditions. Iterations on the oracle result in a probabilistic spotlight on the best high-value hands within all possible outcomes.

Another analogy for an oracle: consider searching a giant library for specific kinds of books. A classical search through an unstructured library would require an exhaustive check on the books one by one. But in a quantum search, you can ask an oracle/librarian a question with a yes/no answer: “Is this the kind of book I’m looking for?” You don’t ask about every book, rather, interference amplifies the “yes” answers across the entire library. After just a few queries, the right books reveal themselves.

Grover’s Algorithm and the Oracle Function

So with inteference amplification fewer queries are needed, and thus a quantum search gives a significant speedup over classical search algorithms: it lets us find an item in an unsorted list of size \(N\) using only about \(\sqrt{N}\) steps. Compared to the \(O(N)\) brute-force linear cost in classical computing, that’s a quadratic advantage.

The heart of Grover's method is the oracle: a function \(f(x)\) that can tell whether a given input \(x\) is a valid solution: where\(f(x)=1\) ; or not valid: where \(f(x)=0\). That is, we don't know if the solution matches until we test it with the oracle. Grover's algorithm prepares a uniform superposition of all possible inputs and uses interference to amplify the probability of measuring a "good" solution. With each iteration, the likelihood of getting the correct answer increases.

For the mathematics involved in Grover’s algorithm you can visit the Wikipedia page, and the discussion at IBM’s Quantum Learning page.

Euchre’s High Value Hands

Euchre uses a reduced deck, 24 cards, with 6 ranks across four suits. It’s a simple game but with some unique rules, especially around trump suits and bowers (“special” Jacks). We will use the game’s rules to define high-value hands in a model using a quantum search algorithm.

In this model, we consider just 3-card hands from a shuffled deck. With 3 cards chosen from 24 that gives \({24\choose 3} = 2024\) possible hands. Note that when using a 3-card hand, there are only 3 face-card hands that meet high-value conditions. These are conditions which only the oracle knows about:

1. The Jack of the trump suit (right bower)

2. The Jack of the same-color suit (left bower)

3. One of Ace, King, or Queen of the trump suit

The goal is to find those three hands for a given trump suit using Grover’s algorithm. This is not done with an algorithm to look for the Jack of Spades or any card. Instead, we encode the rules into an oracle. Grover’s algorithm uses the oracle to probe the entire space of possibilities and, after just a few iterations, it amplifies the bitstrings corresponding to high-value hands. We will see how the cards and hands are encoded, but first a discussion of the design pattern….

The Oracle Design Pattern and Constraints

In quantum computing, oracles are core abstraction tools. If you can define the rules for a solution, you can build a quantum oracle to mark it. While we apply it to Euchre here, an oracle pattern is versatile. Oracles can be adapted for various solutions, from database searches to optimization problems, each with their challenges:

• Sudoku boards with valid numbers:
  (Theoretically possible, but the full 9×9 board space is enormous — over \(6.67\times10^{21}\)combinations → prohibitive oracle complexity and quantum circuit size)

• Optimal arrangements in logistics:
  (Involves factorial search space \(O(N!)\) as with the above, exponential qubit requirements and complex oracles)

• Specific features in large unstructured datasets:
  (Dependent on complexity of logic required for feature-detection where bottlenecks can occur transforming classical data into quantum state. Markings can be across many mutiple-dimensions: e.g. spam and fraud detection)

I previously used constraints to solve the Zebra riddle using symbolic computation. In that case, if solutions existed, they were returned deterministically; if not, the solver reported no solution. With Grover’s algorithm, constraints are embedded in the oracle function, but the algorithm doesn’t return exact solutions in the classical sense. Instead, valid solutions are those whose amplitudes are increased through repeated iterations, making them more likely to be observed upon measurement.

What makes Euchre a nice demo is that it is small enough to simulate, structured enough to encode, and just quirky enough to be fun.

Now that we have covered the high-level concepts, it is time to move over to the code. Let’s see how the oracle is constructed, how the circuit is built in Grover’s algorithm, and finally the results of execution and how the quantum circuit zeroes in on high-value hands.

Binary Encoding of Cards, Deck, and Hands

The Euchre card space we use here will be 4 suits, and 6 ranks. So any card can be represented by 5 bits: <rank=3bits><suit=2bits> So the Jack of Hearts is \(01001\)and the 9 of Spades is \(00000\) etc. Each 3 card hand is represented by 15 bits, and those are the bitstrings that Grover’s algorithm will manipulate.

 class EuchreDeck:
    SUITS = ['♠', '♥', '♦', '♣']
    RANKS = ['9', '10', 'J', 'Q', 'K', 'A']
    CARDS_PER_HAND = 3
    BITS_PER_CARD = 5

    SUIT_BITS = {'♠': '00', '♥': '01', '♦': '10', '♣': '11'}
    RANK_BITS = {'9': '000', '10': '001', 'J': '010', 'Q': '011', 'K': '100', 'A': '101'}
    SAME_COLOR = {'♠': '♣', '♣': '♠', '♥': '♦', '♦': '♥'}

    INV_SUIT_BITS = {v: k for k, v in SUIT_BITS.items()}
    INV_RANK_BITS = {v: k for k, v in RANK_BITS.items()}
    ...

The EuchreDeck class also has methods to (a) shuffle the deck, (b) create the set of all hands \({24\choose3}=2024 \) , and c) encoders and decoders. Here’s some test code to extract a hand from a position (pos=42) of all possible hands, encode/decode etc.

deck = EuchreDeck()
pos = 42
hand = deck.all_hands[pos]
encoded = deck.encode_hand(hand)
bitstring = ''.join(encoded)
decoded = deck.decode_hand(bitstring)
index = deck.find_hand_index(hand)

print(f"Length of all hands: {len(deck.all_hands)}")
print(f"Hand #{pos}: {hand}")
print(f"Encoded: {encoded}")
print(f"Bitstring: {bitstring}")
print(f"Decoded: {decoded}")
print(f"Index in all_hands: {index}")

Length of all hands: 2024
Hand #42: (('J', '♥'), ('9', '♦'), ('J', '♦'))
Encoded: ['01001', '00010', '01010']
Bitstring: 010010001001010
Decoded: (('J', '♥'), ('9', '♦'), ('J', '♦'))
Index in all_hands: 42

You might ask “hey, if there is already a find_hand_index method, can’t we just use that to search for the high value hands?” No, we can’t. Because we don’t know the high value hands, only the oracle knows those rules. Until Grover’s algorithm finishes amplifying the correct bitstrings, we have no way of knowing which hands are the high value hands. Once the amplified bitstring is measured, for this demonstration we use find_hand_index() to locate it in the list of all possible hands.

Marking High Value Euchre Hands

With Euchre a suit is picked as trump, and two special Jacks (called “bowers") have high value. The two Jacks: 1) Jack in the trump suit (right bower) and 2) the Jack in the other suit of the same colour as the trump suit (left bower). The final third card in the high value hands are the King, Queen, and Ace from the trump suit. So given a trump suit and the Euchre deck, a hand of high value cards can be encoded in 3 bitstrings of length 15, and there are three high value hands. These bitstrings are used to create the circuit in the Grover Oracle.

def high_hands_bitstrings(trump: str, deck: EuchreDeck):
    """
    Generate list of bitstrings for 3 high hands for a certain trump.
    e.g. for hearts we have these: 
    1: (('J', '♥'), ('J', '♦'), ('A', '♥'))
    2: (('J', '♥'), ('J', '♦'), ('K', '♥'))
    3: (('J', '♥'), ('J', '♦'), ('Q', '♥'))
    bitstrings =>
    ['010010101010101', '010010101010001', '010010101001101']
    """
    left = deck.SAME_COLOR[trump]
    right_bower = deck.encode_card('J', trump)
    left_bower = deck.encode_card('J', left)
    high_trumps = [deck.encode_card(rank, trump) for rank in ['A', 'K', 'Q']]

    high_hands = []  
    for high in high_trumps:
        hand = right_bower + left_bower + high  
        high_hands.append(hand)
    return high_hands

>>> deck = EuchreDeck()
>>> high_hands_bitstrings('♥', deck)
['010010101010101', '010010101010001', '010010101001101']
>>> for i in range(3): print(deck.decode_hand(high_hands_bitstrings('♥', deck)[i])) 
(('J', '♥'), ('J', '♦'), ('A', '♥'))
(('J', '♥'), ('J', '♦'), ('K', '♥'))
(('J', '♥'), ('J', '♦'), ('Q', '♥'))

Creating an Oracle and Circuit with Qiskit

Now that we have marked the bits for the high value hands, we must create the Grover oracle. We will use IBM’s Qiskit SDK. There are two ways to create the Grover circuit:

1. QuantumCircuit

2. PhaseOracle

Both methods require bit reversal due to Qiskit’s bit ordering. Using QuantumCircuit the bits are used directly and a QuantumCircuit object is created. WIth PhaseOracle the bits are used to create a logical formula and a PhaseOracle object is created. Both of these objects are Oracle objects. The logical formula is a boolean expression which when passed into PhaseOracle will create an oracle corresponding to the marked states.

def bitstrings_to_formula(bitstrings: list[str]) -> str:
    """
    Convert bitstring list to logical formula. Use with PhaseOracle.
    e.g 
    convert bitstring list ["101...", "010...", ...] 
    to logical formula string: (q0 & ~q1 & q2 & ...) | (~q3 & q4 & ~q5 & ...) | (...)
    """
    terms = []
    for bstring in bitstrings:
        bits = []
        for idx, bit in enumerate(bstring):
            t = '' if bit == '1' else '~'
            bits.append(f'{t}q{idx}')
        term = '(' + ' & '.join(bits) + ')'
        terms.append(term)

    formula = ' | '.join(terms)
    return formula

The logical formula is a string where bits are represented not a 1s and 0s rather as a string of \(q \) variable corresponding to the bits: e.g.

$$1011, 0100 \rightarrow \text{(q0 & ~q1 & q2 & q3) | (~q4 & q5 & ~q6 & ~q7)}$$

For this case the cards are 5 bits each and the hand is 3 cards, so bits \(q0 \rightarrow q14\) are used for each of the three hands.

def grover_oracle(marked_bitstrings: list[str], 
                  phase_oracle: bool = False) -> Union[PhaseOracle,QuantumCircuit]:
    """ 
    Given marked bitstrings create Grover's oracle:
    - PhaseOracle or QuantumCircuit 
    """
    reverse_marked = [hand[::-1] for hand in marked_bitstrings]  # Qiskit has reversed bit ordering 
    if phase_oracle:
        logical_formula = bitstrings_to_formula(reverse_marked)
        return PhaseOracle(logical_formula)
    else:
        n = len(marked_bitstrings[0])
        qc = QuantumCircuit(n)
        for bstring in reverse_marked:
            indices = [i for i, b in enumerate(bstring) if b == '0']
            qc.x(indices)  # Flip zeroes to ones
            qc.compose(MCMTGate(ZGate(), n - 1, 1), inplace=True)
            qc.x(indices)  # Flip back
        return qc

Once the Grover Oracle is created it can be used in the creation of the GroverOperator:

deck = EuchreDeck()
trump = '♦'
marked = high_hands_bitstrings(trump, deck)
the_oracle = grover_oracle(marked_bitstrings=marked, phase_oracle=False) 
grover_op = GroverOperator(the_oracle)

Once the operator is ready, it can be used to build the complete circuit, and the simulation can be run:

qc = QuantumCircuit(n_qubits)
qc.h(range(n_qubits))  # Create equal superposition
qc.compose(grover_op.power(optimal_iters), inplace=True)  # Set iterations
qc.measure_all()

sampler = Sampler()
sampler.options.default_shots = 1024
result = sampler.run([qc]).result()

When the run is completed we can print the resulting distribution:

dist = result.quasi_dists[0]
top = OrderedDict(sorted(dist.items(), key=lambda x: -x[1])[:20])
decoded_top = {}
for k, v in top.items():
    bitstring = format(k, f"0{n_qubits}b")
    hand = deck.decode_hand(bitstring)
    if hand:
        index = deck.find_hand_index(hand)
        hand_str = ' '.join([rank + suit for rank, suit in hand])
        label = f"{hand_str} @ {index}"
        print(label, f"P({v})")
        decoded_top[label] = v

plot_distribution(decoded_top, title="High Value Euchre Hands and Index")

Here the result with only 10 iterations: we can see that the 3 high value hands for diamonds have been amplified.

Iterations used this run: 10
High Value Euchre Hands, Index, Probability
J♦ J♥ K♦ @ 1474 P(0.0185546875)
J♦ J♥ A♦ @ 1235 P(0.0126953125)
J♦ J♥ Q♦ @ 144 P(0.0126953125)
A♥ K♦ K♦ @ None P(0.001953125)
A♣ K♣ 9♣ @ 496 P(0.001953125)
J♥ K♥ Q♣ @ 1149 P(0.001953125)
A♣ A♠ K♥ @ 275 P(0.001953125)
Q♦ Q♠ 9♦ @ 185 P(0.001953125)
Q♣ A♠ K♥ @ 319 P(0.001953125)
9♣ 10♣ 9♥ @ 643 P(0.0009765625)
K♦ J♥ K♥ @ 1113 P(0.0009765625)

Optimal Iterations

Notice that there is a hand which is not found in the set of all hand combinations, noted by: A♥ K♦ K♦ @ None. This is because the entire space of 15 bits can be in the result set, but the actual hand combinations do not have two Diamond Kings. If we perform more iterations those anomalies go away.

The optimal number of iterations for Grover’s for a unique or multiple search can be proven. In this case there are marked 3 solutions and based on the proof, we have the following:

n_qubits = len(marked[0])
num_solutions = len(marked)
optimal_iters = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_solutions / 2**n_qubits)))
)

When optimal iterations are done we see that only the 3 high value hands are left:

Optimal iterations : 82
Iterations used this run: 82
High Value Euchre Hands, Index, Probability
J♦ J♥ A♦ @ 1235 P(0.3466796875)
J♦ J♥ Q♦ @ 144 P(0.333984375)
J♦ J♥ K♦ @ 1474 P(0.3193359375)

Using PhaseOracle

The PhaseOracle method requires the tweedledum package. This package currently cannot be installed from the PyPi installer, and had to be built manually for Mac Apple Silicon. So I had to build a local wheel and after some minor tweaking got a successful build. The use of PhaseOracle fits well into this solution because the constraint for this oracle is well defined as a boolean expression.

Running on Real Quantum Hardware

This example executed the algorithm on a circuit within a simulator. To run this on real quantum hardware requires selecting a backend and transpiling the circuit to run it on an IBM Runtime. Once the circuit is trans with Qiskit it can be run on a real backend in IBM Quantum. An IBM Quantum key is used for an account, and a channel service is either created and accessed. I have an implementation of this in the GitHub notebook and it is in the debugging phase, something isn’t quite working correctly!

Conclusion

This Casual Chronicle celebrated the 100th birthday of quantum mechanics by pairing Grover’s quantum search algorithm with the rules of Euchre to zero in on high-value hands.

It started with the basics: how quantum search works, how oracles define rules for the search, and how to encode a deck of 24 Euchre cards and thousands of possible hands into bitstrings. Those concepts are combined into a quantum oracle to mark three of the highest value hands for a given trump.

Once the encodings have been defined the Qiskit SDK is used to build the oracle, run Grover’s algorithm, and then a simulator is run to watch the high value hands “rise” to the top, with just a handful of iterations. With less than the optimal number of iterations an invalid hand with two similar cards showed up with a low probability factor. Two different methods can be used to create the oracle, one with the coding a QuantumCircuit directly from the encoded bits, and another method which uses a PhaseOracle and a logical formula similar to boolean constraint logic.

The math behind the Grover’s algorithm was mostly left out of this discussion as this was intended to cover the coding involved. The Qiskit code can easily be modified to run on an IBM Quantum Backend, but at this time running it on actual hardware is work in progress….

Thanks for reading ! —carl—

https://github.com/carlek/my-qiskit/blob/main/grovers-euchre.ipynb

https://learning.quantum.ibm.com/tutorial/grovers-algorithm