Quantum Algorithms with Qiskit

Introduction to Quantum Algorithms #

Quantum algorithms leverage quantum mechanical phenomena like superposition and entanglement to solve problems more efficiently than classical algorithms. In this section, we’ll implement several fundamental quantum algorithms using Qiskit.

Deutsch-Jozsa Algorithm #

The Deutsch-Jozsa algorithm determines whether a function is constant or balanced with just one query, whereas a classical algorithm would need multiple queries.

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator

def deutsch_jozsa(oracle_type='balanced'):
    """
    Implements the Deutsch-Jozsa algorithm
    oracle_type: 'constant' or 'balanced'
    """
    # Create circuit with n qubits + 1 ancilla
    n = 3  # number of input qubits
    qc = QuantumCircuit(n + 1, n)
    
    # Initialize ancilla qubit to |1⟩
    qc.x(n)
    
    # Apply Hadamard gates to all qubits
    qc.h(range(n + 1))
    qc.barrier()
    
    # Apply oracle
    if oracle_type == 'constant':
        # Constant oracle (do nothing or flip all)
        pass  # Identity operation
    else:
        # Balanced oracle example
        for i in range(n):
            qc.cx(i, n)
    
    qc.barrier()
    
    # Apply Hadamard gates to input qubits
    qc.h(range(n))
    
    # Measure
    qc.measure(range(n), range(n))
    
    return qc

# Run the algorithm
qc = deutsch_jozsa('balanced')
simulator = AerSimulator()
job = simulator.run(qc, shots=1024)
result = job.result()
counts = result.get_counts()

print("Deutsch-Jozsa results:", counts)
# If all 0s: function is constant
# Otherwise: function is balanced

Bernstein-Vazirani Algorithm #

This algorithm finds a hidden binary string with a single query, compared to n queries classically.

def bernstein_vazirani(hidden_string='101'):
    """
    Finds the hidden string in one query
    hidden_string: binary string to find
    """
    n = len(hidden_string)
    qc = QuantumCircuit(n + 1, n)
    
    # Initialize ancilla to |1⟩
    qc.x(n)
    
    # Apply Hadamard gates
    qc.h(range(n + 1))
    qc.barrier()
    
    # Apply oracle based on hidden string
    for i, bit in enumerate(reversed(hidden_string)):
        if bit == '1':
            qc.cx(i, n)
    
    qc.barrier()
    
    # Apply Hadamard gates to input qubits
    qc.h(range(n))
    
    # Measure
    qc.measure(range(n), range(n))
    
    return qc

# Example usage
hidden = '101'
qc = bernstein_vazirani(hidden)
simulator = AerSimulator()
job = simulator.run(qc, shots=1)
result = job.result()
counts = result.get_counts()

print(f"Hidden string found: {list(counts.keys())[0]}")

Grover’s Algorithm #

Grover’s algorithm searches an unsorted database of N items in O(√N) time, providing quadratic speedup over classical search.

import math
from qiskit.circuit.library import GroverOperator
from qiskit import QuantumCircuit

def grover_search(marked_states, num_qubits=3):
    """
    Implements Grover's search algorithm
    marked_states: list of marked states (e.g., ['101', '110'])
    num_qubits: number of qubits
    """
    # Create oracle
    oracle = QuantumCircuit(num_qubits)
    for target in marked_states:
        # Flip phase of target state
        rev_target = target[::-1]
        # Apply X gates to qubits that should be 0
        for i, bit in enumerate(rev_target):
            if bit == '0':
                oracle.x(i)
        
        # Multi-controlled Z gate
        oracle.h(num_qubits - 1)
        oracle.mcx(list(range(num_qubits - 1)), num_qubits - 1)
        oracle.h(num_qubits - 1)
        
        # Undo X gates
        for i, bit in enumerate(rev_target):
            if bit == '0':
                oracle.x(i)
    
    # Create full Grover circuit
    qc = QuantumCircuit(num_qubits, num_qubits)
    
    # Initialize to equal superposition
    qc.h(range(num_qubits))
    
    # Calculate optimal number of iterations
    num_solutions = len(marked_states)
    total_states = 2**num_qubits
    iterations = int(math.pi/4 * math.sqrt(total_states/num_solutions))
    
    # Apply Grover iterations
    for _ in range(iterations):
        # Apply oracle
        qc.compose(oracle, inplace=True)
        
        # Apply diffusion operator
        qc.h(range(num_qubits))
        qc.x(range(num_qubits))
        qc.h(num_qubits - 1)
        qc.mcx(list(range(num_qubits - 1)), num_qubits - 1)
        qc.h(num_qubits - 1)
        qc.x(range(num_qubits))
        qc.h(range(num_qubits))
    
    qc.measure_all()
    
    return qc

# Example: Search for '101' in 3-qubit space
qc = grover_search(['101'], num_qubits=3)
simulator = AerSimulator()
job = simulator.run(qc, shots=1024)
result = job.result()
counts = result.get_counts()

from qiskit.visualization import plot_histogram
plot_histogram(counts)
print("Grover's search results:", counts)

Quantum Fourier Transform (QFT) #

The Quantum Fourier Transform is a key component in many quantum algorithms, including Shor’s algorithm.

import numpy as np

def qft(n):
    """
    Creates a QFT circuit for n qubits
    """
    qc = QuantumCircuit(n)
    
    for j in range(n):
        # Apply Hadamard gate
        qc.h(j)
        
        # Apply controlled phase rotations
        for k in range(j + 1, n):
            qc.cp(2 * np.pi / (2**(k - j + 1)), k, j)
    
    # Swap qubits to reverse order
    for i in range(n // 2):
        qc.swap(i, n - i - 1)
    
    return qc

# Create QFT circuit
qc = qft(4)
qc.draw('mpl')

Inverse QFT #

def inverse_qft(n):
    """
    Creates an inverse QFT circuit
    """
    qc = qft(n)
    return qc.inverse()

Quantum Phase Estimation #

Estimates the phase (eigenvalue) of a unitary operator.

def quantum_phase_estimation(unitary, precision_qubits=3):
    """
    Performs quantum phase estimation
    unitary: the unitary gate to estimate phase of
    precision_qubits: number of qubits for precision
    """
    # Total qubits = precision + eigenstate qubits
    num_qubits = precision_qubits + 1
    qc = QuantumCircuit(num_qubits, precision_qubits)
    
    # Initialize eigenstate (last qubit)
    qc.x(precision_qubits)
    
    # Apply Hadamard to precision qubits
    for i in range(precision_qubits):
        qc.h(i)
    
    # Controlled unitary operations
    repetitions = 1
    for counting_qubit in range(precision_qubits):
        for _ in range(repetitions):
            # Apply controlled unitary
            qc.cp(2 * np.pi / 4, counting_qubit, precision_qubits)
        repetitions *= 2
    
    # Apply inverse QFT
    qc.append(inverse_qft(precision_qubits), range(precision_qubits))
    
    # Measure precision qubits
    qc.measure(range(precision_qubits), range(precision_qubits))
    
    return qc

# Example usage
qc = quantum_phase_estimation(None, precision_qubits=4)

Variational Quantum Eigensolver (VQE) #

VQE is a hybrid quantum-classical algorithm for finding ground state energies.

from qiskit.circuit import Parameter
from qiskit.primitives import Estimator
from scipy.optimize import minimize
import numpy as np

def create_ansatz(num_qubits):
    """
    Creates a parameterized ansatz circuit
    """
    qc = QuantumCircuit(num_qubits)
    
    # Parameters
    params = [Parameter(f'θ{i}') for i in range(num_qubits * 2)]
    
    # Layer 1: Rotation gates
    for i in range(num_qubits):
        qc.ry(params[i], i)
    
    # Entangling layer
    for i in range(num_qubits - 1):
        qc.cx(i, i + 1)
    
    # Layer 2: More rotations
    for i in range(num_qubits):
        qc.ry(params[num_qubits + i], i)
    
    return qc, params

# Create ansatz
ansatz, params = create_ansatz(2)
print(ansatz)

Quantum Approximate Optimization Algorithm (QAOA) #

QAOA solves combinatorial optimization problems.

def qaoa_circuit(num_qubits, beta, gamma):
    """
    Creates a QAOA circuit
    beta: mixer parameter
    gamma: cost parameter
    """
    qc = QuantumCircuit(num_qubits)
    
    # Initial state: equal superposition
    qc.h(range(num_qubits))
    
    # Problem-specific cost Hamiltonian (example: MaxCut)
    # Apply ZZ interactions
    for i in range(num_qubits - 1):
        qc.rzz(2 * gamma, i, i + 1)
    
    # Mixer Hamiltonian
    for i in range(num_qubits):
        qc.rx(2 * beta, i)
    
    return qc

# Example QAOA circuit
qc = qaoa_circuit(4, beta=0.5, gamma=1.0)
qc.draw('mpl')

Using Qiskit’s Algorithm Library #

Qiskit provides pre-built implementations of many algorithms:

from qiskit.algorithms import VQE, QAOA
from qiskit.algorithms.optimizers import SLSQP, COBYLA
from qiskit.circuit.library import TwoLocal
from qiskit.primitives import Sampler

# Example: Using built-in VQE
optimizer = SLSQP(maxiter=100)
ansatz = TwoLocal(2, 'ry', 'cz', reps=2)

# Note: This is a simplified example
# In practice, you'd also define a Hamiltonian

Practice Exercises #

Try implementing these yourself:

  1. Simon’s Algorithm: Find the hidden period of a function
  2. Shor’s Algorithm: Factor a small number (e.g., 15)
  3. HHL Algorithm: Solve a 2x2 linear system
  4. Custom Oracle: Design your own oracle for Grover’s algorithm

Next Steps #

Now that you understand basic quantum algorithms:

  • Explore quantum machine learning algorithms
  • Learn about error mitigation techniques
  • Optimize algorithms for real quantum hardware
  • Study quantum advantage and complexity theory

In the next section, we’ll cover advanced Qiskit features and real hardware execution!