Quantum – Circuits – Bellagio – Definition

Introduction

This post provides a definition of the Bellagio scheduling problem that will be solved in the following posts using a Wave Number quantum circuit. The Wave Numbers Bellagio circuit has been adapted from the solution in Quantum Computing Program Next-Gen Computers for Hard, Real-World Applications.

Problem Definition

Jimmy Kimmel performs only at Aladdin and Bellagio.
Bill Maher performs only at Bellagio and Caesars.
Trevor Noah performs only at Caesars and Aladdin
Schedule needed where no 2 artists scheduled at same venue on same day

Logic Definition for Day 1 at the Aladdin

The quantum state of j^v represents true and j^{^}represents false.

Three Boolean variables (true or false variables) k, m, n are defined as follows:

k means that Jimmy Kimmel does Bellagio on Day 1 then the Aladdin on Day 2
k‾ means that Kimmel does them in opposite order: Aladdin on Day 1 then the Bellagio on Day 2.
m means that Bill Maher does Bellagio on Day 1 then Caesars on Day 2
m‾ means that Maher does them in opposite order: Caesars on Day 1 then the Bellagio on Day 2.
n means that Trevor Noah does Aladdin on Day 1 then Caesars on Day 2
n‾ means that Noah does them in opposite order: Caesars on Day 1 then the Aladdin on Day 2.

Boolean logic expressions are set up that ensure that no two artists are scheduled at the same hotel on the same day—the conflict constraints. For example:

On Day 1 Kimmel and Noah cannot perform at the same time at the Aladdin. This restriction results in the following logic expression:
- Aladdin on Day 1: ⌐ (k‾ ∧ n) = k ∨ n‾
  - Not (Kimmel at the Aladdin on Day 1 and Noah at the Aladdin on Day 1)
  - Simplified to Kimmel at the Bellagio on Day 1 or Noah at Caesars on Day 1

The symbol ∧ stands for the Logical AND, ∨ for Logical OR, and ⌐ is Logical NOT. The left hand side of the first relation states that Kimmel performing at Aladdin on Day 1 (k‾ ) and Noah at Aladdin on Day 1 ( n ) cannot be true at the same time.

The right hand side is its simplification via De Morgan’s rule that states:

Not(A and B) = Not(A) or Not(B) and
Not(A or B) = Not(A) and Not(B)

Logic for Other Slots

The logic expressions for the other slots can be defined similarly:

Aladdin on Day 2: ⌐ (k ∧ n‾) = k‾ ∨ n
- Not (Kimmel at the Aladdin on Day 2 and Noah at the Aladdin on Day 2)
- Simplified as Kimmel at the Bellagio on Day 2 or Noah at Caesars on Day 2
Bellagio on Day 1: ⌐ (k ∧ m) = k‾ ∨ m‾
- Not (Kimmel at the Bellagio on Day 1 and Maher at the Bellagio on Day 1)
- Simplified as Kimmel at the Aladdin on Day 1 or Maher at Caesars on Day 1
Bellagio on Day 2: ⌐ (k‾ ∧ m‾) = k ∨ m
- Not (Kimmel at the Bellagio on Day 2 and Maher at the Bellagio on Day 2)
- Simplified as Kimmel at the Aladdin on Day 2 or Maher at Caesars on Day 2
Caesars on Day 1: ⌐ (m‾ ∧ n‾) = m ∨ n
- Not (Maher at Caesars on Day 1 and Noah at Caesars on Day 1)
- Simplified as Maher at the Bellagio on Day 1 and Noah at the Aladdin on Day 1
Caesars on Day 2: ⌐ (m ∧ n) = m‾ ∨ n‾
- Not (Maher at Caesars on Day 2 and Noah at Caesars on Day 2)
- Simplified as Maher at the Bellagio on Day 2 or Noah at Aladdin on Day 2

Complete Logic for Valid Schedule

Each hotel uses only 2 of the artists. The logic for each hotel for each night ensures that one of the two performers is at another hotel, leaving the slot free for the other.

For a valid schedule, all these logic expressions must be true. i.e.

(k ∨ ‾n) ∧ (k‾ ∨ n) ∧ (k‾ ∨ m‾) ∧ (k ∨ m) ∧ (m ∨ n) ∧ (m‾ ∨ ‾n) = 1

The following quantum circuit solves this problem for Kimmel and Maher at the Bellagio for days 1 and 2 only and covers the following logic:

(k‾ ∨ m‾) ∧ (k ∨ m) = 1

i.e. (Kimmel in the Bellagio on Day 2 or Maher in the Bellagio on Day 2) and (Kimmel in the Bellagio on Day 1 or Maher in the Bellagio on Day 1). Note that the first condition could be met with both Kimmel and Maher at the Bellagio on day 2. However, this would mean that the second condition could not be met as neither could make the Bellagio on Day 2.

Circuit Notation Definition

X represents the σx or NOT gate and Z the σz gate.

Dots identify the control bits in CNOT and CCNOT gates and link to the target qubit by lines. A circle with a cross within identifies the target qubit.

H is the Haadamard gate and it works on individual qubits. However, each application of a Haadamard gate doubles the number of multipart qubits.

Combinations of j^{^},^–j^{^}, j^v or ^–j^v values make up each multipart qubit. The j element of these values is left out in the diagrams in order to make the multipart qubits easier to deal with.

The Bellagio quantum circuit uses the problem definition, logic definition and circuit notations above.

Next: Bellagio Circuit Part 1

Previous: Bell States

Share to: