Category: Uncategorized

Quantum Computing: Grover’s Algorithm – Inversion About the Mean

Grover’s Algorithm: Exact Mathematical Evolution

Full 3-Qubit Matrix Interference Walkthrough

What is Grover’s Algorithm? Grover’s algorithm is a quantum search procedure that locates a marked item in an unsorted list of N items in O(√N) oracle queries — a quadratic speedup over any classical approach. For N = 8 (3 qubits), this means roughly ⌊π/4 × √8⌋ = 2 optimal iterations before the probability of measuring the target state peaks.

This walkthrough tracks the exact amplitude of every basis state through each gate operation for the 3-qubit case, with target state |101>. All arithmetic is shown so each step can be verified by hand.

Structure of each iteration (Grover operator G):

  • Oracle Uf — Phase-flips the target state: |x> → -|x> if f(x) = 1, otherwise |x> → |x>.
  • Diffusion operator D = H⊗n(2|0><0| − I)H⊗n — Reflects all amplitudes about their mean, amplifying the marked state at the expense of the others.

Key insight: The oracle introduces destructive interference at the target, which the diffusion operator then converts into constructive interference by inverting amplitudes about their mean. Each iteration rotates the state vector by an angle 2θ closer to the target, where sin(θ) = 1/√N.

Circuit Overview — 3 Qubits, Target |101⟩
Init Diffusion 1 Diffusion 2
|0⟩H Uf HZ0H Uf HZ0H M
|0⟩H   H H   H H M
|0⟩H   H H   H H M
Iteration 1 Iteration 2 · optimal
H = Hadamard Uf = Oracle (phase-flips target) Z0 = 2|0⟩⟨0|−I M = Measure

Phase 0: Initialization

Steps 1 & 2: Apply H⊗3 to |000> to create a uniform superposition over all 8 basis states. Because each single-qubit Hadamard maps |0> to (|0>+|1>)/√2, applying all three simultaneously yields equal amplitude 1/√8 ≈ 0.3535 for every state. This is the starting point — every state is equally likely, and the algorithm has no preference yet.

|ψinit> = 1/√8 [ |000> + |001> + |010> + |011> + |100> + |101> + |110> + |111> ]

Hadamard Reference (Standard Signs)

The 8×8 Walsh-Hadamard matrix defines the sign pattern when H⊗3 is applied to any basis state. Element (i, j) has sign (−1)popcount(i AND j) — i.e., the number of bit positions where both row state and column state have a 1. The actual amplitude contribution is this sign divided by √8. This table is used in every Hadamard step below: each row corresponds to one input basis state, and its sign pattern determines how it distributes into all 8 output states.

Basis State000001010011100101110111
H|000>++++++++
H|001>+–+–+–+–
H|010>++––++––
H|011>+––++––+
H|100>++++––––
H|101>+–+––+–+
H|110>++––––++
H|111>+––+–++–

Round 1: [Oracle → Diffusion]

Step 3: Oracle Uf — The oracle recognises |101> as the marked state and applies a phase kickback, flipping its amplitude from +1/√8 to −1/√8. All other amplitudes remain unchanged. Physically, this encodes “this is the target” purely in phase — no measurement is made, so the superposition is preserved.

Step 4.1: Round 1 First Hadamard (H)

The diffusion operator begins by mapping from the computational basis back into the Hadamard basis. Each input state |x> with amplitude ax contributes ax/√8 to every output column, with sign given by the reference table. For all non-target states ax = +1/√8, so each cell = (+1/√8)×(Sign/√8) = Sign/8. For the oracle-marked |101>, the amplitude is −1/√8, so the entire row is sign-inverted (highlighted in red). The Net Result row is the vertical sum of all 8 rows for each column.

Source (Post-Oracle)000001010011100101110111
+H|000> (1/√8)+18+18+18+18+18+18+18+18
+H|001> (1/√8)+18-18+18-18+18-18+18-18
+H|010> (1/√8)+18+18-18-18+18+18-18-18
+H|011> (1/√8)+18-18-18+18+18-18-18+18
+H|100> (1/√8)+18+18+18+18-18-18-18-18
-H|101> (-1/√8)-18+18-18+18+18-18+18-18
+H|110> (1/√8)+18+18-18-18-18-18+18+18
+H|111> (1/√8)+18-18-18+18-18+18+18-18
Net Result 4.1+68+28-28+28+28-28+28-28

Step 4.2: Round 1 Phase Flip (Z on non-|000>)

This step implements the 2|0><0|−I operator in the computational basis. In practice it means: keep |000>’s amplitude unchanged, and negate every other state. This is the heart of inversion-about-the-mean: because the |000> column accumulated the largest positive amplitude in Step 4.1 (reflecting the mean of all amplitudes before the first H), flipping everything else relative to it creates the inversion effect that will boost the target in the next step.

State000001010011100101110111
Amp (Post-Z)+68-28+28-28-28+28-28+28

Step 4.3: Round 1 Second Hadamard (H)

The second H maps the Hadamard-basis amplitudes from Step 4.2 back to the computational basis, completing the diffusion operator. Each post-Z amplitude contributes to every output column via the reference sign table, multiplied by 1/√8, giving denominators of 8√8. Summing column |101> yields +208√8 ≈ 0.884 — a dramatic amplification from the initial 0.354 — while all other states settle to +48√8 ≈ 0.177. One iteration is complete.

Source (Post-Z)000001010011100101110111
+H|000> (68)+68√8+68√8+68√8+68√8+68√8+68√8+68√8+68√8
-H|001> (-28)-28√8+28√8-28√8+28√8-28√8+28√8-28√8+28√8
+H|010> (28)+28√8+28√8-28√8-28√8+28√8+28√8-28√8-28√8
-H|011> (-28)-28√8+28√8+28√8-28√8-28√8+28√8+28√8-28√8
-H|100> (-28)-28√8-28√8-28√8-28√8+28√8+28√8+28√8+28√8
+H|101> (28)+28√8-28√8+28√8-28√8-28√8+28√8-28√8+28√8
-H|110> (-28)-28√8-28√8+28√8+28√8+28√8+28√8-28√8-28√8
+H|111> (28)+28√8-28√8-28√8+28√8-28√8+28√8+28√8-28√8
Net Result (R1)+48√8+48√8+48√8+48√8+48√8+208√8+48√8+48√8
Decimal (R1)0.1770.1770.1770.1770.1770.8840.1770.177

Round 2: [Oracle → Diffusion]

Step 5: Oracle Uf — The oracle is applied again to the post-R1 state. |101> now carries a much larger amplitude (+208√8), so the phase flip to −208√8 creates a far more pronounced imbalance. The 7 non-target states each carry only +48√8. This large asymmetry is what will drive even stronger constructive interference in the diffusion step.

Step 6.1: Round 2 First Hadamard (H)

Each amplitude is multiplied by 1/√8 as it spreads across the 8 columns via the reference sign table. The denominator becomes 8√8 × √8 = 64. The 7 uniform states (+48√8) form balanced Walsh-Hadamard rows that cancel perfectly for all non-|000> columns — only the oracle-perturbed |101> row breaks the symmetry, contributing an extra −24 or +24 to each non-zero column (depending on the H sign for that bit pattern). Column |000> is special: all 8 rows contribute positively, giving +864.

Source (Post-Oracle)000001010011100101110111
+H|000> (48√8)+464+464+464+464+464+464+464+464
+H|001> (48√8)+464-464+464-464+464-464+464-464
+H|010> (48√8)+464+464-464-464+464+464-464-464
+H|011> (48√8)+464-464-464+464+464-464-464+464
+H|100> (48√8)+464+464+464+464-464-464-464-464
-H|101> (-208√8)-2064+2064-2064+2064+2064-2064+2064-2064
+H|110> (48√8)+464+464-464-464-464-464+464+464
+H|111> (48√8)+464-464-464+464-464+464+464-464
Net Result 6.1+864+2464-2464+2464+2464-2464+2464-2464

Step 6.2: Phase Flip (Z on non-|000>)

Same operation as Step 4.2: negate every amplitude except |000>. The |000> column retains its +864 value. All other states flip sign, converting e.g. +2464 → −2464. This primes the second Hadamard to route amplitude toward the target state.

State000001010011100101110111
Amp (Post-Z)+864-2464+2464-2464-2464+2464-2464+2464

Step 6.3: Round 2 Second Hadamard (H)

The final H of the diffusion operator maps the post-Z amplitudes back to the computational basis. Each amplitude propagates through the Hadamard sign table with denominator 64√8. Column |101> receives a constructive sum of +17664√8 ≈ 0.972 — near-certain success. The non-target states all land at −1664√8 ≈ −0.088, where the negative sign carries no measurement consequence. This is the optimal stopping point for 3-qubit Grover search: stopping here gives the highest possible P(|101>).

Source (Post-Z)000001010011100101110111
+H|000> (864)+864√8+864√8+864√8+864√8+864√8+864√8+864√8+864√8
-H|001> (-2464)-2464√8+2464√8-2464√8+2464√8-2464√8+2464√8-2464√8+2464√8
+H|010> (2464)+2464√8+2464√8-2464√8-2464√8+2464√8+2464√8-2464√8-2464√8
-H|011> (-2464)-2464√8+2464√8+2464√8-2464√8-2464√8+2464√8+2464√8-2464√8
-H|100> (-2464)-2464√8-2464√8-2464√8-2464√8+2464√8+2464√8+2464√8+2464√8
+H|101> (2464)+2464√8-2464√8+2464√8-2464√8-2464√8+2464√8-2464√8+2464√8
-H|110> (-2464)-2464√8-2464√8+2464√8+2464√8+2464√8+2464√8-2464√8-2464√8
+H|111> (2464)+2464√8-2464√8-2464√8+2464√8-2464√8+2464√8+2464√8-2464√8
Net Result (R2)-1664√8-1664√8-1664√8-1664√8-1664√8+17664√8-1664√8-1664√8
Decimal (R2)-0.088-0.088-0.088-0.088-0.088+0.972-0.088-0.088
Success Probability: P(101) = |0.9724|2 ≈ 94.5%

Round 3: [Oracle → Diffusion] (The Overcooking Effect)

Step 7: Oracle Uf — With P(|101>) at 94.5%, one more iteration is one too many. The oracle again flips |101>’s amplitude: +17664√8 → −17664√8. The 7 non-target states each remain at −1664√8. The state vector has been rotated 2θ past its peak, and a third diffusion step will push it further away from the target, not closer.

Step 8.1: Round 3 First Hadamard (H)

The denominator grows to 512 (= 64√8 × √8). All 8 input amplitudes are now negative (after the oracle flip, |101> is −17664√8 and the rest are −1664√8), so the |000> column accumulates a strongly negative sum (−288512). The non-|000> columns are dominated by the large −|101> row contribution, which is sign-inverted from the reference table and therefore contributes ±176512. The net result is a lopsided distribution that the phase flip will convert into a push away from the target.

Source (Post-Oracle)000001010011100101110111
-H|000> (-1664√8)-16512-16512-16512-16512-16512-16512-16512-16512
-H|001> (-1664√8)-16512+16512-16512+16512-16512+16512-16512+16512
-H|010> (-1664√8)-16512-16512+16512+16512-16512-16512+16512+16512
-H|011> (-1664√8)-16512+16512+16512-16512-16512+16512+16512-16512
-H|100> (-1664√8)-16512-16512-16512-16512+16512+16512+16512+16512
-H|101> (-17664√8)-176512+176512-176512+176512+176512-176512+176512-176512
-H|110> (-1664√8)-16512-16512+16512+16512+16512+16512-16512-16512
-H|111> (-1664√8)-16512+16512+16512-16512+16512-16512-16512+16512
Net Result 8.1-288512+160512-160512+160512+160512-160512+160512-160512

Step 8.2: Round 3 Phase Flip (Z on non-|000>)

The |000> amplitude (−288512) is preserved. All other amplitudes flip sign. Notice that after R2 the non-target states had small negative amplitudes; after the phase flip here they become positive (+160512), while the target column was −160512 and now becomes +160512 as well — the diffusion has lost its asymmetry and will no longer strongly favour |101>.

State000001010011100101110111
Amp (Post-Z)-288512-160512+160512-160512-160512+160512-160512+160512

Step 8.3: Round 3 Second Hadamard (H)

The second H maps amplitudes back to the computational basis with denominators of 512√8. The large negative |000> amplitude now spreads destructive interference broadly, while the relatively uniform positive amplitudes for the remaining states partially cancel in the |101> column. The result is +832512√8 = +138√8 ≈ +0.575 for |101> and −448512√8 = −78√8 ≈ −0.309 for all non-target states. P(|101>) has fallen to ~33%, demonstrating that iterating past the optimal count hurts. Importantly, |101> still leads every other state by 3×, so a single extra iteration only partially degrades the result — it has not catastrophically lost the solution.

Source (Post-Z)000001010011100101110111
-H|000> (-288512)-288512√8-288512√8-288512√8-288512√8-288512√8-288512√8-288512√8-288512√8
-H|001> (-160512)-160512√8+160512√8-160512√8+160512√8-160512√8+160512√8-160512√8+160512√8
+H|010> (160512)+160512√8+160512√8-160512√8-160512√8+160512√8+160512√8-160512√8-160512√8
-H|011> (-160512)-160512√8+160512√8+160512√8-160512√8-160512√8+160512√8+160512√8-160512√8
-H|100> (-160512)-160512√8-160512√8-160512√8-160512√8+160512√8+160512√8+160512√8+160512√8
+H|101> (160512)+160512√8-160512√8+160512√8-160512√8-160512√8+160512√8-160512√8+160512√8
-H|110> (-160512)-160512√8-160512√8+160512√8+160512√8+160512√8+160512√8-160512√8-160512√8
+H|111> (160512)+160512√8-160512√8-160512√8+160512√8-160512√8+160512√8+160512√8-160512√8
Net Result (R3)-448512√8-448512√8-448512√8-448512√8-448512√8+832512√8-448512√8-448512√8
Simplified (R3)-78√8-78√8-78√8-78√8-78√8+138√8-78√8-78√8
Decimal (R3)-0.309-0.309-0.309-0.309-0.309+0.575-0.309-0.309

⚠ Overcooking Confirmed — But Not Catastrophic

The state vector has rotated past the optimal angle. P(|101>) drops from 94.5% (R2) to 33.0% — a significant fall, but |101> still has more than double the probability of any other state. The algorithm has not “lost” the answer; it has merely de-amplified it. Note also that the target amplitude is still positive (+0.575) — the vector has not crossed zero, it has simply overshot past the maximum. The 33.0% comes directly from the Born rule: P(|101>) = |amplitude|² = |+0.575|² ≈ 0.330.

Streamlining macOS Application Management with Homebrew Cask

macOS users frequently face the challenge of efficiently managing application installations across multiple machines. The traditional approach involves manually downloading disk images, navigating installation wizards, and maintaining applications across systems. Homebrew Cask offers a command-line solution that significantly streamlines this process.

Understanding Homebrew Cask

Homebrew Cask is an extension of Homebrew, the widely-adopted package manager for macOS. While Homebrew manages command-line tools and libraries, Cask extends this functionality to graphical user interface (GUI) applications. This enables system administrators, developers, and power users to install, update, and manage standard macOS applications through terminal commands.

The conventional installation workflow requires multiple steps:

  1. Locating the official download source
  2. Downloading the disk image file
  3. Opening and mounting the disk image
  4. Transferring the application to the Applications folder
  5. Ejecting the disk image
  6. Managing the downloaded installer file
  7. Repeating this process for each required application

Homebrew Cask reduces this to a single command:

brew install --cask google-chrome

The application is then installed automatically with no further user interaction required.

Key Advantages for Professional Workflows

1. Accelerated System Provisioning

Organizations and individual users can maintain installation scripts containing all required applications. A typical enterprise development environment setup might include:

brew install --cask visual-studio-code
brew install --cask docker
brew install --cask slack
brew install --cask zoom
brew install --cask rectangle
brew install --cask iterm2
brew install --cask spotify
brew install --cask vlc

This approach reduces new machine setup time from several hours to approximately 15-20 minutes, depending on network bandwidth and the number of applications being installed.

2. Simplified Update Management

Maintaining current software versions is essential for security compliance and feature availability. Rather than monitoring and updating each application individually, administrators can execute a single command:

brew upgrade --cask

This command updates all Cask-managed applications to their latest versions, ensuring consistent patch management across the system.

3. Complete Application Removal

Standard macOS uninstallation methods often leave residual files including configuration data, cache files, and preference files distributed throughout the file system. Homebrew Cask performs thorough removal:

brew uninstall --cask docker

This ensures complete application removal without orphaned system files.

4. Automation and Standardization

Homebrew Cask’s command-line interface enables scripting and automation. Development teams can create standardized setup scripts ensuring consistent development environments. IT departments can implement automated workstation provisioning workflows. System configurations can be version-controlled in dotfiles repositories, enabling rapid deployment and rollback capabilities.

Recommended Applications by Category

The following applications represent commonly deployed tools across professional environments:

Development Tools

brew install --cask visual-studio-code
brew install --cask iterm2
brew install --cask docker
brew install --cask postman
brew install --cask dbeaver-community

Productivity Applications

brew install --cask rectangle        # Window management
brew install --cask alfred           # Enhanced search functionality
brew install --cask obsidian         # Knowledge management
brew install --cask notion           # Collaborative workspace

Communication Platforms

brew install --cask slack
brew install --cask zoom
brew install --cask discord

System Utilities

brew install --cask the-unarchiver
brew install --cask appcleaner
brew install --cask vlc

Implementation Guide

Organizations and users without an existing Homebrew installation can deploy it with a single command:

/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"

Once Homebrew is installed, Cask functionality is built right in. Just start using brew install --cask commands.

Useful Commands to Know

# Search for an app
brew search --cask chrome

# Get information about an app
brew info --cask visual-studio-code

# List all installed cask apps
brew list --cask

# Update all apps
brew upgrade --cask

# Uninstall an app
brew uninstall --cask slack

A Few Gotchas

Cask isn’t perfect. Here are some things to be aware of:

  • Not every app is available – Popular apps are well-covered, but niche or very new applications might not be in the repository yet
  • App Store apps aren’t included – Apps distributed exclusively through the Mac App Store can’t be installed via Cask
  • Some apps require manual steps – Occasionally, an app needs additional configuration or permissions that Cask can’t automate
  • Updates might lag slightly – Cask maintainers need to update formulas when new versions release, so there can be a brief delay

These are minor inconveniences compared to the time saved.

The Bottom Line

Homebrew Cask has fundamentally changed how I interact with my Mac. What started as a way to avoid repetitive downloads has become an essential part of my workflow. The ability to script, automate, and version-control my application setup means I’m never more than a few commands away from a productive environment.

If you spend any significant time on macOS, especially as a developer or power user, Homebrew Cask is worth learning. Your future self—the one setting up that next new machine—will thank you.

Try It Yourself

Pick three applications you use regularly and install them via Cask. I bet you’ll be hooked by the simplicity. Start with something like:

brew install --cask visual-studio-code
brew install --cask google-chrome  
brew install --cask rectangle

Welcome to a more efficient way of managing your Mac applications.

What’s your favorite Homebrew Cask application? Have you automated your Mac setup? Share your experiences in the comments below!

Quick Guide to n8n

Here is a quick guide on n8n. See also:

Quick guide to Docker
Quick guide to Gnuplot
Quick guide to CVS
Quick guide to nawk
Quick guide to Emacs
Quick guide to Git
Quick guide to NSCC ASPIRE2A

To run n8n from a docker container, first pull the n8n container.

docker pull n8nio/n8n

Set up a persistent storage for the n8n container.

docker volume create n8n_data

Run the n8n docker container.

docker run -it --rm --name n8n -p 5678:5678 -v n8n_data:/home/node/.n8n docker.n8n.io/n8nio/n8n

You can now access n8n on the following local url: http://localhost:5678

Quantum Fourier Transform (QFT) of a Single Qubit is Hadamard Transform

Below is the definition of QFT as illustrated in the YouTube lecture by Abraham Asfaw.

The LaTex code for the equation is as follows and also available here.

Latex
| \tilde{x} \rangle \equiv ~ QFT ~ |x \rangle ~ \equiv \frac{1}{\sqrt{N}}\sum_{y=0}^{N-1}{e^{\frac{2\pi ix y}{N}}} ~| y \rangle

For the one qubit case, N = 21 = 2:

Latex
| \tilde{x} \rangle \equiv ~ QFT ~ |x \rangle ~ \equiv \frac{1}{\sqrt{}N}\sum_{y=0}^{N-1}{e^{\frac{2\pi ix y}{N}}} ~| y \rangle


Latex
\frac{1}{\sqrt{2}}\sum_{y=0}^{1}{e^{\pi ix y}} ~| y \rangle = \frac{1}{\sqrt{2}}[~e^{i \pi x 0}~ | 0 \rangle ~ + ~ e^{i \pi x 1}~| 1 \rangle] = \frac{1}{\sqrt{2}}[~|0\rangle ~+~e^{i \pi x}~|1 \rangle~]

When x = 0:

Latex
QFT~| 0 \rangle = \frac{1}{\sqrt{2}}[~|0\rangle ~+~e^{i \pi 0}~|1 \rangle~] = \frac{1}{\sqrt{2}}[~| 0 \rangle + |1 \rangle~] = |+\rangle

When x = 1:


Latex
QFT~| 1 \rangle = \frac{1}{\sqrt{2}}[~|0\rangle ~+~e^{i \pi 1}~|1 \rangle~] = \frac{1}{\sqrt{2}}[~| 0 \rangle - |1 \rangle~] = |-\rangle

Hence the QFT of a single qubit is essentially the Hadamard transform.