DEV Community: Supreeth Mysore Venkatesh

Navigating into Quantum Computing for Software Engineers

Supreeth Mysore Venkatesh — Tue, 14 Apr 2026 14:40:57 +0000

I made a short video on introducing quantum computing for software engineers.

The goal was to explain the field without hype and without assuming a physics background, more from the perspective of code, algorithms, and real computational use cases.

If you’re curious about quantum but coming from software/dev/CS, this might be a good starting point:

Would love your honest feedback.

Qubit-Efficient Encoding Techniques for Solving QUBO Problems

Supreeth Mysore Venkatesh — Thu, 22 May 2025 16:53:06 +0000

🧠 Introduction

Classical algorithms are already incredibly effective at solving many optimization problems, especially when the number of variables is in the low thousands. However, when scaling up to problems involving tens or hundreds of thousands of binary variables, classical solvers begin to falter due to the combinatorial explosion in the search space.

Quantum computing offers a compelling alternative, not by brute force, but by exploring exponentially large solution spaces in parallel using quantum superposition and entanglement. One popular quantum algorithm for such problems is the Quantum Approximate Optimization Algorithm (QAOA) [3], a textbook example of a variational quantum algorithm (VQA). However, QAOA requires one qubit per binary variable, which becomes prohibitively resource-intensive for large-scale problems.

For instance, solving a QUBO (Quadratic Unconstrained Binary Optimization) problem with 10,000 variables using QAOA would require 10,000 logical qubits — a scale far beyond current quantum hardware capabilities.

🔍 Why Qubit-Efficient Methods?

This demo explores qubit-efficient alternatives to QAOA that are not only suitable for today's NISQ (Noisy Intermediate-Scale Quantum) devices, but also generalizable across combinatorial optimization problems.

We specifically demonstrate these methods in the context of unsupervised image segmentation, by:

Formulating segmentation as a min-cut problem over a graph derived from the image.
Reformulating the min-cut as a QUBO problem.
Solving the QUBO using qubit-efficient VQAs, namely [1]:
- Parametric Gate Encoding (PGE)
- Ancilla Basis Encoding (ABE)
- Adaptive Cost Encoding (ACE)

These methods only require a logarithmic number of qubits with respect to the problem size (i.e., number of binary variables). This makes them scalable and implementable even on near-term quantum hardware. Moreover, the exact graph-based image segmentation technique have been explored also using quantum annealers [2].

While this demo walks through an image segmentation example, the encoding schemes presented here can be applied to any binary combinatorial optimization problem.

Architecture for segmenting an image by transforming it into a graph and solving the corresponding minimum cut as a QUBO problem using variational quantum circuits [1]

Clone the Repository: Begin by cloning the repository to your local machine. Open a terminal/cmd/powershell and run

   git clone https://github.com/supreethmv/Pennylane-ImageSegmentation.git
   cd Pennylane-ImageSegmentation

Install Dependencies: Use the provided requirements.txt to install all necessary libraries. The process may take a few minutes depending on your internet speed and the packages already available in your system.

   pip install -r requirements.txt

Open a jupyter notebook and execute the below python code.

🧱 Import dependencies

We begin by importing the standard Python libraries for graph construction and visualization, and PennyLane modules for quantum circuit construction and simulation. This setup ensures a seamless interface for hybrid quantum-classical processing.

import numpy as np
import networkx as nx
import pennylane as qml
from scipy.optimize import minimize, differential_evolution
import matplotlib.pyplot as plt

from math import ceil, log2
import time

🖼️ Generate an Example Image

To keep things intuitive, we generate a toy grayscale image. This synthetic image will be segmented using quantum algorithms.

We use a simple 4×4 grid for clarity. The pixel intensities will act as a proxy for similarity when we later construct a graph. Each pixel becomes a vertex, and edges represent similarity (e.g., inverse of intensity difference).

height,width = 4,4
image = np.array([
       [0.97,  0.92, 0.05, 0.92],
       [0.93,  0.10, 0.12, 0.93],
       [0.94,  0.15, 0.88, 0.94],
       [0.98,  0.15, 0.10, 0.92]
       ])


plt.imshow(image, interpolation='nearest', cmap=plt.cm.gray, vmin=0, vmax=1)
# plt.axis('off')
plt.xticks([])
plt.yticks([])
plt.show()

🔗 Representing Image as a Graph

Each image is modeled as an undirected weighted grid graph:

Each pixel becomes a node.
An edge exists between neighboring pixels.
The weight reflects similarity (e.g., inverse absolute difference in grayscale values).

This transforms the segmentation task into a minimum cut problem, where the goal is to partition the graph to minimize the sum of cut edge weights.

def image_to_grid_graph(gray_img, sigma=0.5):
  # Convert image to grayscale
  h, w = gray_img.shape
  # Initialize graph nodes and edges
  nodes = np.zeros((h*w, 1))
  edges = []
  nx_elist = []
  # Compute node potentials and edge weights
  min_weight = 1
  max_weight = 0
  for i in range(h*w):
    x, y = i//w, i%w
    nodes[i] = gray_img[x,y]
    if x > 0:
      j = (x-1)*w + y
      weight = 1-np.exp(-((gray_img[x,y] - gray_img[x-1,y])**2) / (2 * sigma**2))
      edges.append((i, j, weight))
      nx_elist.append(((x,y),(x-1,y),np.round(weight,2)))
      if min_weight>weight:min_weight=weight
      if max_weight<weight:max_weight=weight
    if y > 0:
      j = x*w + y-1
      weight = 1-np.exp(-((gray_img[x,y] - gray_img[x,y-1])**2) / (2 * sigma**2))
      edges.append((i, j, weight))
      nx_elist.append(((x,y),(x,y-1),np.round(weight,2)))
      if min_weight>weight:min_weight=weight
      if max_weight<weight:max_weight=weight
  a=-1
  b=1
  if max_weight-min_weight:
    normalized_edges = [(node1,node2,-1*np.round(((b-a)*((edge_weight-min_weight)/(max_weight-min_weight)))+a,2)) for node1,node2,edge_weight in edges]
    normalized_nx_elist = [(node1,node2,-1*np.round(((b-a)*((edge_weight-min_weight)/(max_weight-min_weight)))+a,2)) for node1,node2,edge_weight in nx_elist]
  else:
    normalized_edges = [(node1,node2,-1*np.round(edge_weight,2)) for node1,node2,edge_weight in edges]
    normalized_nx_elist = [(node1,node2,-1*np.round(edge_weight,2)) for node1,node2,edge_weight in nx_elist]
  return nodes, edges, nx_elist, normalized_edges, normalized_nx_elist

pixel_values, elist, nx_elist, normalized_elist, normalized_nx_elist = image_to_grid_graph(image)

pixel_values, normalized_nx_elist

(array([[0.97],
        [0.92],
        [0.05],
        [0.92],
        [0.93],
        [0.1 ],
        [0.12],
        [0.93],
        [0.94],
        [0.15],
        [0.88],
        [0.94],
        [0.98],
        [0.15],
        [0.1 ],
        [0.92]]),
 [((0, 1), (0, 0), np.float64(1.0)),
  ((0, 2), (0, 1), np.float64(-1.0)),
  ((0, 3), (0, 2), np.float64(-1.0)),
  ((1, 0), (0, 0), np.float64(1.0)),
  ((1, 1), (0, 1), np.float64(-0.9)),
  ((1, 1), (1, 0), np.float64(-0.92)),
  ((1, 2), (0, 2), np.float64(0.97)),
  ((1, 2), (1, 1), np.float64(1.0)),
  ((1, 3), (0, 3), np.float64(1.0)),
  ((1, 3), (1, 2), np.float64(-0.87)),
  ((2, 0), (1, 0), np.float64(1.0)),
  ((2, 1), (1, 1), np.float64(1.0)),
  ((2, 1), (2, 0), np.float64(-0.82)),
  ((2, 2), (1, 2), np.float64(-0.77)),
  ((2, 2), (2, 1), np.float64(-0.69)),
  ((2, 3), (1, 3), np.float64(1.0)),
  ((2, 3), (2, 2), np.float64(0.97)),
  ((3, 0), (2, 0), np.float64(1.0)),
  ((3, 1), (2, 1), np.float64(1.0)),
  ((3, 1), (3, 0), np.float64(-0.92)),
  ((3, 2), (2, 2), np.float64(-0.8)),
  ((3, 2), (3, 1), np.float64(1.0)),
  ((3, 3), (2, 3), np.float64(1.0)),
  ((3, 3), (3, 2), np.float64(-0.9))])

G = nx.grid_2d_graph(image.shape[0], image.shape[1])
G.add_weighted_edges_from(normalized_nx_elist)

def draw(G):
  plt.figure(figsize=(6,6))
  default_axes = plt.axes(frameon=True)
  pos = {(x,y):(y,-x) for x,y in G.nodes()}
  nx.draw_networkx(G, pos)
  nodes = nx.draw_networkx_nodes(G, pos, node_color=1-pixel_values,
                  node_size=3000,
                  cmap=plt.cm.Greys, vmin=0, vmax=1)
  nodes.set_edgecolor('k')
  edge_labels = nx.get_edge_attributes(G, "weight")
  nx.draw_networkx_edge_labels(G,
                              pos=pos,
                              edge_labels=edge_labels,
                              font_size=10,
                              font_color='tab:blue')
  plt.axis('off')
draw(G)
plt.show()

🔁 Parametric Gate Encoding (PGE)

In PGE, we directly encode the binary segmentation mask in the rotation parameters of a diagonal gate [4].

Only $\log_2(n)$ qubits are required, which is a huge gain over methods like QAOA that need $O(n)$.

Quantum Circuit:

Apply Hadamard gates to initialize a uniform superposition.
Apply a diagonal gate $U(\vec{\theta})$ whose entries encode binary values using a thresholding function $f(\theta_i)$.
Evaluate the cost function: $$ C(\vec{\theta}) = \langle \psi(\vec{\theta}) | L_G | \psi(\vec{\theta}) \rangle $$ where $L_G$ is the graph Laplacian.

The result is optimized using a classical optimizer, and $\theta_i$ are mapped to bits depending on whether $\theta_i < \pi$ or not.

n = G.number_of_nodes()
n_qubits = int(np.ceil(np.log2(n)))
n_qubits

def R(theta): 
    if abs(theta) > 2*np.pi or abs(theta) < 0:
        theta = abs(theta) - (np.floor(abs(theta)/(2*np.pi))*(2*np.pi))
    return 0 if 0 <= theta < np.pi else 1

# Define a PennyLane quantum device (using default.qubit simulator)
dev = qml.device("default.qubit", wires=n_qubits)

# Quantum circuit as a QNode
@qml.qnode(dev)
def circuit(params, H):
    # N = len(params)
    N = int(np.log2(len(params)))
    for i in range(N):
        qml.Hadamard(wires=i)

    diagonal_elements = [np.exp(1j * np.pi * R(param)) for param in params]
    # qml.DiagonalQubitUnitary(np.diag(diagonal_elements), wires=list(range(N)))
    qml.DiagonalQubitUnitary(diagonal_elements, wires=list(range(N)))

    return qml.expval(qml.Hermitian(H, wires=list(range(N))))

def cost_fn(params, H):
    global optimization_iteration_count
    optimization_iteration_count += 1
    cost = circuit(params, H)
    print(f'@ Iteration {optimization_iteration_count} Cost :', cost)
    return cost

def decode(optimal_params):
    return [R(param) for param in optimal_params]

def objective_value(x, w):
    return np.dot(x, np.dot(w, x))

def new_nisq_algo_solver(G, optimizer_method='Powell', initial_params_seed=123):
    global optimization_iteration_count
    optimization_iteration_count = 0
    n = G.number_of_nodes()
    w = nx.adjacency_matrix(G).todense()
    D_G = np.diag(list(dict(G.degree()).values()))
    A_G = w
    L_G = D_G - A_G
    n_padding = (2**int(np.ceil(np.log2(n)))-n)
    L_G = np.pad(L_G, [(0, n_padding), (0, n_padding) ], mode='constant')
    H = L_G

    np.random.seed(seed=initial_params_seed)
    initial_params = np.random.uniform(low=0.5, high=2*np.pi , size=(n+n_padding))

    result = minimize(
        fun=cost_fn,
        x0=initial_params,
        args=(H,),
        method=optimizer_method,
    )

    optimal_params, expectation_value = result.x, result.fun
    x = np.real(decode(optimal_params))
    x = x[:n]
    cut_value = objective_value(x, w)

    return x, expectation_value, cut_value

binary_solution, expectation_value, cut_value = new_nisq_algo_solver(G, optimizer_method = 'Powell')
binary_solution, expectation_value, cut_value

@ Iteration 1 Cost : 2.7137499999999983
@ Iteration 2 Cost : 2.7137499999999983
@ Iteration 3 Cost : 2.7137499999999983
@ Iteration 4 Cost : 2.7137499999999983
@ Iteration 5 Cost : 2.7137499999999983
.
.
.
@ Iteration 349 Cost : 0.18374999999999986
@ Iteration 350 Cost : 0.18374999999999986
@ Iteration 351 Cost : 0.18374999999999986
@ Iteration 352 Cost : 0.18374999999999986
@ Iteration 353 Cost : 0.18374999999999986

def decode_binary_string(x, height, width):
  mask = np.zeros([height, width])
  for index,segment in enumerate(x):
    mask[index//width,index%width]=segment
  return mask

mask = decode_binary_string(binary_solution, height, width)
plt.imshow(mask, interpolation='nearest', cmap=plt.cm.gray, vmin=0, vmax=1)
plt.xticks([])
plt.yticks([])
plt.show()

The complete mathematical descriptions and implementations of the next two methods ABE and ACE can be found in my personal blogging site available at:

https://www.supreethmv.com/blog/posts/qubit-efficient-encoding/

📄 References

[1] S. M. Venkatesh, A. Macaluso, M. Nuske, M. Klusch, and A. Dengel, "Qubit-Efficient Variational Quantum Algorithms for Image Segmentation," 2024 IEEE International Conference on Quantum Computing and Engineering (QCE), Montreal, QC, Canada, 2024, pp. 450–456. DOI: 10.1109/QCE60285.2024.00059, arXiv:2405.14405

[2] S. M. Venkatesh, A. Macaluso, M. Nuske, M. Klusch and A. Dengel, "Q-Seg: Quantum Annealing-Based Unsupervised Image Segmentation," in IEEE Computer Graphics and Applications, vol. 44, no. 5, pp. 27-39, Sept.-Oct. 2024, doi: 10.1109/MCG.2024.3455012, arXiv:2311.12912.

[3] Farhi, E., Goldstone, J., & Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028.

[4] Rančić, M. J. (2023). Noisy intermediate-scale quantum computing algorithm for solving an n-vertex MaxCut problem with log (n) qubits. Physical Review Research, 5(1), L012021. DOI: 10.1103/PhysRevResearch.5.L012021

[5] Tan, B., Lemonde, M. A., Thanasilp, S., Tangpanitanon, J., & Angelakis, D. G. (2021). Qubit-efficient encoding schemes for binary optimisation problems. Quantum, 5, 454. DOI: 10.22331/q-2021-05-04-454

Discrete Digital Deception: Bits Fooling You

Supreeth Mysore Venkatesh — Thu, 21 Nov 2024 16:26:18 +0000

How tech plays the game, making fake look the same!

Introduction: Welcome to the Matrix!

What’s your screen time today?

We’re living in an increasingly digital world, where nothing is truly continuous. Everything you see, hear, and experience digitally is an approximation, a clever lie designed to trick your senses. Let’s dive into the digital world, where reality is cut into tiny, discrete pieces to fit the rigid framework of 1s and 0s.

From how your computer adds numbers to how your favorite song streams, everything in the digital realm is a deception orchestrated to satisfy our limited human perception. Let’s dive into this fascinating world and uncover the tricks of the digital trade.

Examples of Everyday Digital Trickery

Lights, Camera, Illusion!

Let’s talk about videos. The smoothness of a video is an illusion created by displaying a sequence of still images (frames) rapidly. At 120 frames per second (fps), the video presents a sequence of still images so rapidly that your brain perceives them as smooth motion. Our eyes can’t detect the individual frames beyond a certain threshold, usually around 24–60 fps for most humans. However, your pet might not share this experience because animals like dogs and cats have higher flicker fusion thresholds, meaning they perceive the gaps between frames more easily and see the screen as flickering chaos.

But the illusion isn’t just about the fps of the video. Irrespective of whether you are watching a video or reading this page, the screen also has a refresh rate measured in hertz (Hz). This determines how many times per second the screen updates the displayed content. For example, a screen with a 60Hz refresh rate updates 60 times per second, while a 120Hz screen updates twice as fast. If the fps of the video exceeds the refresh rate of the screen, those extra frames are either skipped or blended, which might degrade the smoothness of motion. Conversely, if the screen’s refresh rate is higher than the fps of the video, it introduces smoother motion, but only up to the limitations of the video content.

In essence, fps is how the software delivers the frames, while refresh rate is how the hardware displays them. For the smoothest experience, they need to work in harmony.

Even a single frame in that video isn’t “continuous” like reality. What looks real to you is just an arrangement of tiny pixels. More pixels = higher resolution = sharper illusion. But zoom in on any pixel, and you realize it’s just a tiny blob of color, hardly the Mona Lisa!

Think of pixels like LEGO bricks. A low-res image is like using chunky blocks to build a castle. It gets the idea across but looks rough. A high-resolution image is like using tiny LEGO pieces for presenting subtle details. Either way, it’s still just LEGO!

Your Ears Are Just as Gullible

Did you know your favorite song is just numbers? Yep, digital audio records sound by taking snapshots of it, typically 44,000 times per second (44.1 kHz). Each snapshot is a single value, and when played back in sequence, it tricks your ears into hearing a smooth melody.

Here’s the twist: even at a live concert with analog instruments, the sound you hear isn’t entirely pure. For a large audience, microphones capture the sound waves, convert them into electrical signals, and loudspeakers recreate them. While the final sound mimics the real thing, it remains an interpretation—one step removed from nature’s true analog form.

The Math: When 1.1 + 2.2 ≠ 3.3

Let’s check with numbers. In the digital world, even basic math can be misleading. If you've ever tried to add 1.1 and 2.2 in Python (or any other programming language), you'll notice the result isn’t exactly 3.3.

1.1 + 2.2 == 3.3

Output:

False

The digital world relies on the IEEE 754 Standard for Floating-Point Arithmetic, a method of representing fractions digitally. This system introduces rounding errors because computers can only store a finite number of decimal places. Think of it as trying to pour a gallon of water into a pint-sized jar.
Instead of dealing with precise values, computers approximate. The result? Slight inaccuracies like the one above. Computers use binary to represent numbers, and binary isn’t great at storing fractions exactly. So, what you’re seeing is the closest approximation.

Think of public transport, like a bus or train, with predetermined stops. Your destination might not match a stop exactly, so you get off at the nearest one and walk the rest of the way. Similarly, computers approximate numbers to the nearest value they can represent, just wish it’s a perfect match.

Impact on Machine Learning Techniques

.
.
.

Are you curious to see the adverse effects on fundamental Data Science practices? Check out the full blog

Full Blog Link: https://www.supreethmv.com/blog/posts/discrete_digital_deception/

Master the Art of Editing AI Content: Tips and Real-Life Examples

Supreeth Mysore Venkatesh — Sun, 10 Nov 2024 23:56:21 +0000

Introduction

There is no honor among thieves. We’re all leaning on Large Language Models, those AI tools that have become the go-to for everything from captions to your social media posts to articulating cover letters for job applications, code documentation to even the conventional search engines. As a researcher who is constantly churning out academic papers, crafting emails, and firing off formal messages, I can confidently say that LLMs make life way easier. But here’s the thing: while these models do a pretty impressive job, they can mess up in subtle ways that give the game away.

And don’t get me wrong, I’m not here to spread conspiracy theories or warn you that AI is going to trigger an apocalypse. Nope, this isn’t that kind of blog. I get it: if I don’t use it, my competitor will, and then they’ll shine just a bit brighter than me. So, what’s the solution? This blog will help you spot those telltale AI blunders and teach you how to tweak the content to sound more human. Plus, I’ll provide you with tips, tools, and plenty of examples to show you how it’s done.

Common Indicators of AI-Generated Text

Ever read something online and had that sudden realization: This sounds way too perfect? Like, maybe it’s a Reddit thread about a pretty mundane topic, and yet, every sentence has flawless grammar, balanced structure, and an oddly patient tone, as if a teacher is walking you through the steps of a simple math problem. Yeah, there’s a good chance that post was written by an AI, like ChatGPT or its fancy cousins.

So, how can you spot these machine-crafted bits of text? Well, grab your coffee (or tea, no judgments here) and let's dive into some telltale signs of AI-generated content.

Overly Polished Language

You know how humans write, sometimes we mess up a bit, maybe toss in a random comma or run on with a thought until we forget the point. AI? Nah, it’s got that spotless, essay-level polish your English teacher dreamed of. If the piece you’re reading sounds like it’s been edited by a robot with OCD, that’s your first clue.

What it looks like:

AI: “It is essential to recognize that achieving balance in one’s daily routine contributes significantly to personal well-being.”
Human: “Balancing your daily routine helps. Seriously, it makes a difference.”
More Examples:
- AI: “The intricacies of the ecosystem must be understood for meaningful preservation.”
- Human: “Yeah, nature’s complicated, but we gotta save it.”

AI-generated content sounds like it’s aiming for that A+ essay. Humans? We sound more like, “Eh, this should do.”

Balanced and Predictable Sentences

Ever notice how some writing has this steady, almost hypnotic flow? Like, every sentence is just the right length, with perfect punctuation. It’s like listening to a song where every note is perfectly on beat. That’s AI. Humans, on the other hand, will throw in a short sentence. Then ramble on in a long, chaotic one that’s borderline a brain dump, you know, just to keep things interesting.

Example:

AI-generated: “The importance of regular exercise cannot be overstated, as it plays a pivotal role in maintaining not only physical but also mental health.”
Human-written: “Exercise is good. It helps you stay healthy and sane, you know? Plus, it’s free therapy.”
More Examples:
- AI: “Effective time management strategies include prioritizing tasks and setting realistic goals.”
- Human: “Want to get stuff done? Pick the urgent things and don’t go nuts with your to-do list.”

Redundant Vocabulary

AI doesn’t have favorites, it uses all the words it knows just to make things sound varied. So, if you’re seeing fancy terms like “pivotal,” “crucial,” and “significant” all in one paragraph, it’s probably AI showing off. Humans? We pick a word and roll with it. If it’s “important,” it’s just important.

Example:

AI-generated: “The pivotal nature of these findings underscores their critical importance and highlights their significant impact.”
Human-written: “This stuff is pretty important. Seriously, it makes a big difference.”
More Examples:
- AI: “The notable outcome demonstrates an essential shift, pointing to crucial advancements in the field.”
- Human: “This change? Yeah, it’s a big deal.”

Curious to see more tips and examples on how to outsmart AI and polish your content with a human touch? Check out the full blog for pro-level editing tricks, free powerful tools, and real-life examples that will transform your writing.

Full Blog Link: https://www.supreethmv.com/blog/posts/ai_generated_text_indicators/

Q-Seg: Quantum Magic for Image Segmentation (Yes, You Heard Right)

Supreeth Mysore Venkatesh — Sat, 09 Nov 2024 05:24:49 +0000

Intro

Let's talk image segmentation. It's basically telling a computer, "Hey, divide this image up so it makes sense." Whether it's for recognizing cats in photos or spotting flood zones from space, segmentation is everywhere, from health diagnostics to satellites.

But here's the kicker, the algorithms keep getting better because of the hardware we're running them on. And guess what? There's a new player on the field: quantum computing.

Motivation (Why Bother?)

So, why the fuss over quantum? Classical image segmentation tools work great if you have high-quality images and plenty of labeled data. But real life's a bit messy. We're talking noisy, uncertain, or unlabeled data that these methods can't always handle well. Just to classify cats or dogs, classical methods need something like 80,000 labeled images to hit 99% accuracy on new data. Now, imagine that level of reliable data for segmentation, where we're classifying each pixel. That's an insane expectation!

And that's where Q-Seg strolls in, cool as a cucumber, ready to solve this problem without breaking a sweat. Think quantum computing meets unsupervised learning. We're talking about using quantum to break down complex images in a way that just wasn't possible before, at least not without some serious computational power and time.

How It Works (The Friendly Version)

Picture It: Imagine an image, now turn it into a graph where each pixel is a little node connected by edges. The weights on these edges tell us if two pixels are similar (neighbors in color, intensity, or texture) or not.
Quantum Twist: Now, this is where the quantum magic happens. We convert this whole thing into a quantum problem called QUBO (that's Quadratic Unconstrained Binary Optimization for the uninitiated). Our quantum computer, like the D-Wave Advantage, takes that huge graph and finds the "minimum cut" - the best way to slice up the image by minimizing the "cost" of cutting those edges.
Result: The result is a beautiful segmentation map - just what we wanted! We used quantum tunneling (yes, that's as cool as it sounds) to sift through an almost infinite number of possibilities and find the global best solution.

A Peek at the Math (Skip If You Dare)

For my math-lovers out there, here’s how we actually make it work. The edge weights between pixels, for example, are calculated using this simple Gaussian metric:

$w'(p_i, p_j) = 1 - \exp\left(-\frac{(I(p_i) - I(p_j))^2}{2\sigma^2}\right)$

Now, don’t worry if that formula looks intense. Think of it this way: higher values mean pixels look alike, and low values mean they don’t.

Want the full guide? Check out my detailed blog for a deep dive into the method, code, and implementation tips!

References:
Full Blog: https://www.supreethmv.com/blog/posts/Q-Seg
Paper: https://ieeexplore.ieee.org/document/10669751
arXiv: https://arxiv.org/abs/2311.12912
Code: https://github.com/supreethmv/Q-Seg

Square and Fair: The Role of Square Images in Deep Learning

Supreeth Mysore Venkatesh — Sat, 01 Jun 2024 16:20:37 +0000

In the realm of deep learning, especially when working with convolutional neural networks (CNNs), you might have noticed that square images are often preferred. This preference isn't arbitrary; it stems from several practical considerations that enhance the efficiency and simplicity of neural network architectures. In this blog, we will explore the reasons behind this preference and illustrate the concepts with Python code examples.
Let's break down the main points and include Python code snippets to justify each statement.

1. Streamlined Convolutional Operations

Many CNN architectures leverage convolutional operations, applying filters or kernels to local regions of an input image. Square input dimensions simplify these operations by ensuring that the filters can efficiently traverse the entire image without complications associated with uneven dimensions.

Python Example:

import torch
import torch.nn as nn

# Example convolution operation
conv = nn.Conv2d(in_channels=1, out_channels=1, kernel_size=3, stride=1, padding=1)
input_image = torch.randn(1, 1, 28, 28)  # Square image: 28x28
output = conv(input_image)
print(f"Output shape for square input: {output.shape}")

This code demonstrates how a convolutional layer processes a square input image, ensuring consistent traversal.

2. Efficient Parameter Sharing

CNNs benefit from parameter sharing, where the same filter weights are applied across different regions of the input. Square images provide a consistent grid structure, facilitating parameter sharing and ensuring that learned features generalize well.

Python Example:

# Continuing from the previous example
filters = conv.weight.data
print(f"Filter shape: {filters.shape}")

Here, the filter shape remains consistent, allowing parameter sharing across the square image.

3. Simplified Pooling Operations

Pooling layers, such as max pooling or average pooling, are used in CNNs to downsample feature maps and reduce spatial dimensions. Square images make pooling operations straightforward and uniform, simplifying the reduction process.

Python Example:

pool = nn.MaxPool2d(kernel_size=2, stride=2)
pooled_output = pool(output)
print(f"Pooled output shape: {pooled_output.shape}")

This code snippet shows max pooling on a square input, demonstrating the uniform reduction in dimensions.

4. Compatibility with Pre-Trained Models

Many pre-trained CNN architectures and models are designed to handle square input shapes. Using square images ensures compatibility with these architectures, making it easier to leverage pre-trained models.

Python Example:

from torchvision import models

# Example using a pre-trained model
model = models.resnet18(pretrained=True)
input_image = torch.randn(1, 3, 224, 224)  # Square image: 224x224
output = model(input_image)
print(f"Output shape for ResNet with square input: {output.shape}")

This demonstrates compatibility with a pre-trained ResNet model, which expects square input images.

5. Regularization Techniques

Data augmentation involves applying random transformations to input images during training. Square images simplify the implementation of these techniques, ensuring consistent transformations.

Python Example:

from torchvision import transforms

# Example data augmentation pipeline
transform = transforms.Compose([
    transforms.RandomRotation(30),
    transforms.RandomHorizontalFlip(),
    transforms.ToTensor()
])

# Apply transformations to a sample image
from PIL import Image
sample_image = Image.open('sample.jpg').resize((224, 224))  # Ensure the image is square
transformed_image = transform(sample_image)

Here, the transformations are consistently applied to a square image.

6. Aligning with Standard Image Sizes

Square images are commonly encountered in standard image sizes, making them a convenient choice for a wide range of applications, datasets, and image sources.

Example:

Standard datasets like MNIST (28x28) and ImageNet (224x224) use square images, highlighting their widespread use and compatibility.

Conclusion:

While square images offer several advantages, neural networks can handle non-square images as well. The choice of image dimensions often depends on the specific requirements of the task and the architecture being used. However, the simplicity and compatibility associated with square images make them a preferred choice in many deep learning applications.

Quantum Algorithm Implementation: Finding the Best Deals

Supreeth Mysore Venkatesh — Mon, 27 May 2024 01:30:03 +0000

Introduction

The similarity between the rich and the poor is that both love a good bargain—just at different stores. Whether you’re shopping at Louis Vuitton or a local flea market, everyone is on the lookout for the best deals. But what if you could use cutting-edge technology to optimize your shopping experience?
Imagine trying to bundle purchases to maximize discounts, but the options are so numerous, forget about manually evaluating each one, it's impossible even for today's supercomputers. However, this problem can be tackled using quantum computing, specifically with the BILP-Q algorithm. Let's dive into how this works.

Understanding the Basics

What is the Problem?

Think of this as a shopping challenge. You have four items to buy: a webcam, shoes, headphones, and socks. Each item or combination of items has a different discount. The goal? Find the best combination of bundles to minimize your total cost.

Classical Approach vs. Quantum Approach:

Traditionally, solving this involves evaluating all possible combinations of items, which quickly becomes impractical as the number of items increases. This is a classical NP-Hard problem in AI called the Coalition Structure Generation (CSG) problem which has vital applications in cooperative game theory, multi-agent systems, and microeconomics.
Quantum computing, however, can handle this complexity more efficiently.

Introducing BILP-Q

What is BILP-Q?

BILP-Q stands for Binary Integer Linear Programming - Quantum. It transforms our shopping problem into a Quadratic Unconstrained Binary Optimization (QUBO) problem, which quantum computers can solve effectively using algorithms like Quantum Approximate Optimization Algorithm (QAOA).

Example Scenario

Imagine you want to buy four items: a webcam, shoes, headphones, and socks. Here’s how the discounts for different bundles look:

Single items:

Webcam: $30
Shoes: $40
Headphones: $25
Socks: $15

Bundles of two items:

Webcam & Shoes: $50
Webcam & Headphones: $40
Webcam & Socks: $50
Shoes & Headphones: $55
Shoes & Socks: $45
Headphones & Socks: $45

Bundles of three items:

Webcam, Shoes & Headphones: $90
Webcam, Shoes & Socks: $95
Webcam, Headphones & Socks: $75
Shoes, Headphones & Socks: $85

All four items:

Webcam, Shoes, Headphones & Socks: $105

Your goal is to buy all four items with the maximum discount.
For formal definitions of the problem and mathematical details, please refer to the original paper of BILP-Q.

Visual Representation of the solution space

The following diagram shows all possible ways to purchase the four items, along with their total costs. Each level represents a different number of groups (coalitions).

Manually checking each possible combination is tedious, so we use BILP-Q to find the optimal solution.

Walkthrough of the Example

Setting Up the Problem:

Install qiskit

pip install qiskit
pip install qiskit_optimization

Clone/download the BILP-Q official repository and import the below python scripts:

import Utils_Solvers
import Utils_CSG

Define the Problem Instance:

We will enumerate the items as follows:
1 for Webcam,
2 for Shoes,
3 for Headphones, and
4 for Socks.
Here’s how you can initialize the values of the bundles:

# Define the cost of each bundle
coalition_values = {
    '1': 30,
    '2': 40,
    '3': 25,
    '4': 15,
    '1,2': 50,
    '1,3': 40,
    '1,4': 50,
    '2,3': 55,
    '2,4': 45,
    '3,4': 45,
    '1,2,3': 90,
    '1,2,4': 95,
    '1,3,4': 75,
    '2,3,4': 85,
    '1,2,3,4': 105
}

Convert to BILP:

We convert the CSG problem to a Binary Integer Linear Programming (BILP) problem:

c, S, b = Utils_CSG.convert_to_BILP(coalition_values)

Convert to QUBO:

Next, we convert the BILP problem to a Quadratic Unconstrained Binary Optimization (QUBO) problem:

import numpy as np

qubo_penalty = 50 * -1
linear, quadratic = Utils_CSG.get_QUBO_coeffs(c, S, b, qubo_penalty)

Q = np.zeros([len(linear), len(linear)])

# Diagonal elements
for key, value in linear.items():
    Q[int(key.split('_')[1]), int(key.split('_')[1])] = value

# Non-diagonal elements
for key, value in quadratic.items():
    Q[int(key[0].split('_')[1]), int(key[1].split('_')[1])] = value / 2
    Q[int(key[1].split('_')[1]), int(key[0].split('_')[1])] = value / 2

Solving QUBO Using QAOA:

We use QAOA to solve the QUBO problem:

#@title Default title text
backend = BasicAer.get_backend('qasm_simulator') 
optimizer = COBYLA(maxiter=100, rhobeg=2, tol=1.5)
qubo = create_QUBO(linear, quadratic)

p=1
init = [0.,0.]

qaoa_mes = QAOA(optimizer=optimizer, reps=p, quantum_instance=backend, initial_point=init)
qaoa = MinimumEigenOptimizer(qaoa_mes)  # using QAOA
qaoa_result = qaoa.solve(qubo)

solution = qaoa_result.x
print(f'Solution: {solution}')

Decoding the Solution:

The solution x is a binary string of size $2^n - 1$ , where each bit represents a non-empty subset of the items and the positions marked 1 will be considered. For four items, the subsets are:

Webcam
Shoes
Headphones
Socks
Webcam, Shoes
Webcam, Headphones
Webcam, Socks
Shoes, Headphones
Shoes, Socks
Headphones, Socks
Webcam, Shoes, Headphones
Webcam, Shoes, Socks
Webcam, Headphones, Socks
Shoes, Headphones, Socks
Webcam, Shoes, Headphones, Socks

For example, the solution is obtained will look like 000001001000000.
Parsing the binary string from left to right, we select the 6th subset {Webcam, Headphones} and the 9th subset {Shoes, Socks} as the optimal bundles to purchase.

Visualizing the Quantum Circuit

Finally, display the quantum circuit used in QAOA:

qaoa_mes.get_optimal_circuit().draw('mpl')

The Challenge of the Problem

Although this is a very hard problem, the size of the input is also exponential compared to the number of agents (items in this case). For $n = 4$ items, the input was a dictionary of prices for each possible bundle, which totals $2^n−1 = 2^4−1=15$ .

Thus, in the next post, we will explore induced subgraph games, where the problem setting is more practical, but the complexity of finding the optimal solution is still hard for classical computers.

Conclusion

In this post, we explored how a quantum algorithm can tackle complex optimization problems efficiently. We have modeled a very primitive scenario while the actual problem is based on intelligent agents and typically not items. There are more realistic coalition formation use-cases that can be implemented such as peer-to-peer energy trading, logistics, wireless sensor networks and see how quantum computing can simplify the decision-making process.

Quantum computing is still emerging, but its potential to solve complex optimization problems is immense. As quantum technology advances, we can expect more efficient solutions to problems that are currently infeasible for classical computers.

References

Supreeth Mysore Venkatesh, Antonio Macaluso, and Matthias Klusch. "BILP-Q: Quantum Coalition Structure Generation." 19th ACM International Conference on Computing Frontiers (CF’22), May 17–19, 2022, Torino, Italy. Paper Link, Preprint on arXiv
Github repository: https://github.com/supreethmv/BILP-Q

Join the Discussion

I wrote this post to make the concepts of quantum computing more accessible and to showcase its real-world applications. Whether you're a seasoned tech enthusiast or just curious about new technologies, I believe there's something valuable for everyone here.

Feel free to leave your questions, thoughts, or feedback in the comments below. I'd love to hear about your experiences, any challenges you face with optimization problems or other topics you’d like to learn more about.