Meta tags:
description=Use Qiskit s optimization module to formulate and solve combinatorial problems: Max-Cut, knapsack, and TSP using QAOA and the MinimumEigenOptimizer.;
author=QuantumComputingCourses.com;

Headings (most frequently used words):

the, qubo, problem, qaoa, with, quantum, max, cut, hardware, to, optimization, qiskit, on, graph, circuit, optimizer, comparison, penalty, for, solving, quadraticprogram, node, knapsack, landscape, classical, and, grover, scaling, summary, objective, terms, example, in, inspecting, coefficients, cobyla, too, variables, problems, why, installing, formulation, theory, class, conversion, details, traveling, salesman, cities, vehicle, routing, structure, parameter, visualization, types, performance, numpysolver, warm, starting, recursive, running, real, runtime, analysis, common, mistakes, related, tutorials, get, one, email, week, converting, constraints, matrix, depth, convert, solve, what, converter, handles, expansion, compare, against, brute, force, binary, variable, encoding, vrp, components, explicit, ring, interpreting, derivative, free, spsa, stochastic, perturbation, bfgs, gradient, based, key, observations, vs, connecting, ibm, transpiling, target, error, mitigation, practical, considerations, table, honest, assessment, using, few, layers, not, increasing, maxiter, forgetting, that, minimumeigenoptimizer, minimizes, misinterpreting, result, fval, sign, choosing, small, expecting, advantage, current, ready, go, deeper, learn, reference, careers, about, adding, integer, quadratic, statistics, substituting, worked, verifying, mathematical, form,

Text of the page (most frequently used words):
the (215), qaoa (93), for (92), from (77), import (71), and (62), print (59), sampler (53), #quantum (51), with (50), problem (49), optimizer (43), qubo (42), optimization (40), qiskit (35), variables (34), qiskit_optimization (34), objective (32), hardware (31), cobyla (28), this (27), circuit (27), cut (27), penalty (27), quadraticprogram (26), result (26), max (25), binary (24), minimumeigenoptimizer (23), that (23), values (23), linear (22), classical (21), graph (21), problems (21), reps (21), maxiter (21), solve (20), converter (20), small (19), quadraticprogramtoqubo (19), variable (18), fval (18), node (17), you (17), algorithms (17), qiskit_algorithms (17), use (16), exact (16), weights (16), maxcut (16), grover (15), constraints (15), value (15), binary_var (15), real (14), where (14), spsa (14), convert (14), depth (14), each (14), courses (13), landscape (13), knapsack (13), solution (13), approximation (13), constraint (13), guide (12), one (12), parameter (12), qubits (12), are (12), vrp (12), quadratic (12), parameters (12), optimizers (12), qp2 (12), qubit (11), algorithm (11), requires (11), gradient (11), not (11), too (11), len (11), range (11), which (11), name (11), ratio (11), exact_result (11), tutorials (10), all (10), read (10), gates (10), comparison (10), more (10), when (10), can (10), tsp (10), current (10), minimize (10), than (10), numpyminimumeigensolver (10), original (10), x_i (10), free (9), build (9), structure (9), count (9), function (9), set (9), number (9), maximize (9), edges (9), noise (9), capacity (9), graphs (9), gamma (9), beta (9), your (8), terms (8), first (8), runtime (8), starting (8), cities (8), primitives (8), like (8), based (8), best (8), convergence (8), slack (8), converters (8), coefficients (8), maximization (8), 200 (8), qp_ks (8), export_as_lp_string (8), min (7), why (7), vehicle (7), conversion (7), solutions (7), solver (7), has (7), layers (7), provides (7), options (7), backend (7), sense (7), to_quadratic_program (7), applications (7), g_ring (7), total (7), get_num_vars (7), integer (7), qp_verify (7), qp3 (7), performance (6), about (6), practical (6), visualization (6), any (6), nisq (6), 100 (6), large (6), minimizes (6), but (6), often (6), better (6), good (6), error (6), resilience_level (6), exactly (6), uses (6), qp_grover (6), encoding (6), random (6), networkx (6), shot (6), energy (6), ring (6), energy_grid (6), offset (6), into (6), customers (6), depot (6), 2026 (5), types (5), compare (5), learning (5), need (5), speedup (5), beginner (5), common (5), scaling (5), warm (5), formulation (5), yes (5), brute (5), force (5), size (5), scales (5), most (5), instances (5), bfgs (5), helps (5), understanding (5), how (5), none (5), automatically (5), cost (5), handles (5), increasing (5), regular (5), only (5), circuits (5), high (5), search (5), nodes (5), noisy (5), simulator (5), mitigation (5), rhs (5), linear_constraint (5), converges (5), qaoa_val (5), seed (5), per (5), betas (5), min_idx (5), gammas (5), plt (5), operator (5), n_points (5), edge (5), matrix (5), vehicles (5), inequality (5), form (5), x_2 (5), x_1 (5), x_0 (5), policy (4), com (4), framework (4), computing (4), tools (4), what (4), get (4), ibm (4), fault (4), tolerant (4), complete (4), time (4), summary (4), mistakes (4), analysis (4), running (4), recursive (4), routing (4), class (4), theory (4), multiple (4), structured (4), increase (4), works (4), well (4), noiseless (4), initialization (4), strategies (4), same (4), some (4), because (4), true (4), actual (4), handle (4), always (4), setting (4), ratios (4), improves (4), using (4), low (4), specific (4), variational (4), run (4), additional (4), samplerv2 (4), continuous (4), does (4), optimal (4), find (4), exact_solver (4), minimum (4), layer (4), every (4), exact_val (4), numpy (4), estimates (4), evaluations (4), maximum (4), to_ising (4), qubo_ring (4), qp_ring (4), maxcut_ring (4), qp_vrp (4), get_num_linear_constraints (4), distances (4), solving (4), best_val (4), combo (4), sum (4), becomes (4), qubo_ks (4), add (4), diagonal (4), hello (4), world (4), hadamard (3), amazon (3), editorial (3), careers (3), programming (3), glossary (3), reference (3), case (3), studies (3), learn (3), new (3), cirq (3), pennylane (3), related (3), numpysolver (3), traveling (3), salesman (3), details (3), installing (3), these (3), browse (3), verify (3), then (3), behavior (3), decomposition (3), rqaoa (3), very (3), methods (3), simulation (3), choose (3), between (3), gives (3), workflow (3), define (3), research (3), even (3), auto (3), may (3), finds (3), violate (3), internally (3), negate (3), manually (3), without (3), directly (3), poor (3), few (3), quality (3), have (3), deep (3), approaches (3), path (3), reliably (3), since (3), after (3), 300 (3), keep (3), overhead (3), accurate (3), readout (3), local (3), qiskitruntimeservice (3), once (3), example (3), larger (3), heuristic (3), grover_result (3), groveroptimizer (3), weight_limit (3), adds (3), instance (3), quickly (3), items (3), gnm_random_graph (3), robust (3), counts (3), approximate (3), stochastic (3), perturbation (3), two (3), makes (3), space (3), contains (3), out (3), matplotlib (3), interactions (3), times (3), unitary (3), get_num_binary_vars (3), distance (3), best_combo (3), total_value (3), weight (3), encoded (3), ceil (3), log2 (3), equality (3), violating (3), takes (3), equals (3), off (3), x_j (3), coefficient (3), unconstrained (3), combinatorial (3), braket (3), cookies (2), improve (2), affiliate (2), see (2), llc (2), quantumcomputingcourses (2), books (2), podcasts (2), events (2), faq (2), company (2), jobs (2), interview (2), certifications (2), salary (2), bloch (2), sphere (2), timeline (2), news (2), frameworks (2), paths (2), references (2), quantumcomputing (2), email (2), week (2), magic (2), states (2), minutes (2), deutsch (2), jozsa (2), explained (2), python (2), language (2), intermediate (2), level (2), estimator (2), guides (2), coursera (2), edx (2), udemy (2), brilliant (2), deeper (2), tutorial (2), sections (2), building (2), workflows (2), start (2), against (2), key (2), quadratically (2), until (2), limited (2), approach (2), needed (2), simulators (2), technique (2), understand (2), expand (2), encodes (2), debug (2), implementations (2), solvers (2), advantage (2), means (2), let (2), improvement (2), choosing (2), positive (2), negative (2), stored (2), negated (2), instead (2), maximizes (2), negates (2), pass (2), must (2), converge (2), default (2), especially (2), before (2), adding (2), point (2), achieves (2), 6924 (2), 7559 (2), honest (2), expectations (2), families (2), speedups (2), shallow (2), enabling (2), proven (2), over (2), approximately (2), interaction (2), native (2), cnots (2), depends (2), connectivity (2), coupling (2), maps (2), due (2), feasible (2), lower (2), target (2), just (2), much (2), zero (2), speed (2), shots (2), qiskit_ibm_runtime (2), supports (2), hw_optimizer (2), qaoa_hw (2), sampler_runtime (2), selected (2), false (2), service (2), ibm_quantum (2), channel (2), rqaoa_result (2), rqaoa_optimizer (2), recursiveminimumeigenoptimizer (2), fixes (2), reducing (2), flat (2), warm_result (2), warm_qaoa (2), warmstartqaoaoptimizer (2), above (2), useful (2), guarantees (2), numpy_solver (2), optimum (2), grover_opt (2), num_value_qubits (2), depending (2), others (2), degree (2), creating (2), number_of_edges (2), run_maxcut_qaoa (2), return (2), qaoa_result (2), qaoa_solver (2), maxcut_app (2), 500 (2), moderate (2), excellent (2), statevector (2), smooth (2), gradients (2), lbfgsb (2), l_bfgs_b (2), method (2), information (2), choice (2), expensive (2), main (2), different (2), expectation (2), regions (2), corresponds (2), global (2), valleys (2), several (2), plot (2), fig (2), qaoa_eval (2), evaluate (2), enumerate (2), linspace (2), cycle_graph (2), translators (2), number_of_nodes (2), finding (2), repeated (2), apply (2), mixer (2), bitstrings (2), explore (2), parameterized (2), cnot (2), state (2), create (2), superposition (2), customer (2), already (2), assignment (2), n_customers (2), n_vehicles (2), vehiclerouting (2), array (2), locations (2), location (2), given (2), visited (2), beyond (2), qp_tsp (2), asks (2), city (2), total_weight (2), zip (2), product (2), expansion (2), extra (2), added (2), numerical (2), converted (2), inspecting (2), term (2), minimization (2), object (2), partition (2), expanding (2), consider (2), mathematical (2), reduced (2), substitute_variables (2), upperbound (2), lowerbound (2), entry (2), q_ii (2), q_ij (2), x_3 (2), entries (2), prerequisites (2), wave (2), accept, decline, experience, track, our, cookie, privacy, disclosure, associate, earns, qualifying, purchases, contact, talent, pool, post, job, team, training, questions, cheatsheets, history, docs, independent, catalog, published, curated, anyone, 241, 220, 112, subscribe, address, worth, taking, changed, spam, unsubscribe, anytime, introduction, cern, paid, machine, qureca, qtindu, openhpi, jun, updated, glance, page, api, next, previous, advanced, continue, ready, share, was, helpful, own, gradually, complexity, intuition, bottleneck, worse, formulations, arrives, techniques, offers, alternative, answer, selection, preferred, reserved, bridge, become, optionally, wrapping, eigensolver, interface, other, express, program, outperform, tool, production, today, gurobi, cplex, scipy, optimize, expecting, converter_auto, usually, safe, converter_strong, explicitly, converter_weak, outweighs, stores, misinterpreting, sign, correct, negation, wrong, negating, yourself, forgetting, 1000, qaoa_good, give, room, qaoa_bad, insufficient, looks, try, qaoa_deeper, qaoa_shallow, while, least, matters, understood, alternatives, will, change, important, certain, admit, though, been, conclusively, demonstrated, ansatze, hybrid, achieve, corrected, allow, sizes, could, offer, exceeds, execute, heuristics, simulated, annealing, tabu, semidefinite, relaxations, routinely, thousands, seconds, assessment, estimated, sparse, swap, insertions, transpilation, 600, marginal, 048, 576, 120, 024, table, essential, realistic, expect, compared, establish, prefer, backends, rates, accumulate, considerations, workloads, meaningful, excessive, slowest, extrapolation, balance, accuracy, fastest, noisiest, sampler_mitigated, 4000, execution, enables, errors, largest, sources, through, option, hw_result, uncomment, transpile, match, map, gate, transpiling, min_num_qubits, least_busy, select, save_account, token, your_api_token, save, credentials, generate_preset_pass_manager, transpiler, preset_passmanagers, connecting, switching, changes, cloud, processors, min_num_vars_optimizer, min_num_vars, iteratively, correlated, pair, enough, eps, relax_for_pre_solver, pre_solver, relaxation, sdp, initialize, near, improving, generally, considered, goemans, williamson, 878, bar, beat, general, earlier, benchmarking, significantly, arithmetic, evaluating, limits, however, rather, answers, era, ancillas, sqrt, principle, dependent, type, feature, controls, precision, grover_knapsack, unlike, provable, typically, cancels, benefit, irregular, breaks, symmetries, exploits, varies, widely, easy, hard, easier, highly, symmetric, studied, benchmark, expected, theoretical, farhi, goldstone, gutmann, 2014, observations, complete_graph, random_regular_graph, erdos, renyi, test, fair, else, def, heavily, section, compares, three, illustrate, differences, sims, fast, approx, faster, avoid, cause, erratic, qaoa_lbfgsb, poorly, maxfun, quasi, newton, hessian, landscapes, inherently, compatible, environments, qaoa_spsa, learning_rate, simultaneous, iteration, regardless, efficient, dimensional, spaces, medium, drawback, slow, many, qaoa_cobyla, info, disp, tolerance, tol, iterations, constrained, approximations, require, making, finite, sampling, derivative, critical, component, searches, suit, scenarios, motivates, interpolation, strategy, zhou, 2020, transfer, produce, nearly, uniform, uninformative, phenomenon, affects, barren, plateau, deepest, valley, achievable, basin, repeats, period, symmetry, comes, periodicity, trapped, suboptimal, their, minima, characteristic, periodic, features, stand, interpreting, found, show, 150, dpi, qaoa_landscape, png, savefig, tight_layout, markersize, unravel_index, argmin, shape, mark, label, colorbar, set_title, eta, set_ylabel, amma, set_xlabel, viridis, cmap, shading, pcolormesh, figsize, subplots, eigenvalue, compute_minimum_eigenvalue, initial_point, fixed, zeros, scan, 30x30, grid, sparsepauliop, quantum_info, pyplot, possible, visualize, full, heatmap, reveals, explains, configurations, decomposed, ising, hamiltonian, qaoa_ring, explicit, gamma_1, gamma_p, beta_1, beta_p, task, measure, computational, basis, obtain, candidate, measurement, drives, transitions, implemented, equivalent, equal, consists, components, reason, requirements, resource, hungry, devices, focuses, break, smaller, subproblems, route, cost_matrix, num_nodes, num_vehicles, index, 363, indicate, travels, plus, grows, generalizes, routes, travel, minimized, accurately, steps, shortest, tour, visits, step, guarantee, longer, repeat, itertools, pack, exceeding, doubles, impacts, resources, required, hilbert, bits, knapsack_qubo_demo, examine, expands, leave, selects, override, leading, violations, instability, used, factor, gets, introducing, penalized, way, penalties, things, behind, scenes, its, internals, returns, interpret, via, application, builds, sets, cross, boundary, naturally, side, should, check, exactly_one, verify_example, simple, subject, encode, worked, verifying, constant, appears, output, fixing, constants, fix, leaving, substitution_demo, known, testing, know, part, advance, substituting, names, get_num_quadratic_constraints, statistics, quadratic_objective, note, during, continuous_var, integer_var, integer_example, objectives, rich, inspection, my_problem, central, abstraction, incident, differs, contributes, endpoint, absolute, costs, gain, rule, thumb, creates, issues, lets, satisfied, violated, squared, violation, pushing, away, definition, standard, make, converting, act, capture, pairwise, q_01, q_02, q_12, q_00, q_11, q_22, vector, upper, triangular, diving, code, sits, center, package, implementation, later, install, pip, toolkit, familiar, hand, configuration, exponentially, possibilities, candidates, measuring, resulting, distribution, algebra, basics, concepts, entanglement, proficiency, module, formulate, jan, series, home, troubleshooting, prep, universities, career, cheat, sheets, migration, pinball, ocean, tket, pyquil, shor, rigetti, quera, azure, quantinuum, ionq, google, providers, course, platforms, skip, content,

Text of the page (random words):
hat integer and continuous variables get encoded into binary variables during qubo conversion an integer variable with range 0 5 requires ceil log2 6 3 binary variables this encoding overhead means that integer variables expand the qubit count quadratic terms in the objective qp2 quadraticprogram quadratic_objective qp2 binary_var x0 qp2 binary_var x1 qp2 binary_var x2 minimize 2 x0 3 x1 x2 4 x0 x1 2 x1 x2 qp2 minimize linear x0 2 x1 3 x2 1 quadratic x0 x1 4 x1 x2 2 print qp2 export_as_lp_string inspecting problem statistics print f number of variables qp2 get_num_vars print f number of binary variables qp2 get_num_binary_vars print f number of linear constraints qp2 get_num_linear_constraints print f number of quadratic constraints qp2 get_num_quadratic_constraints print f variable names v name for v in qp2 variables print f objective sense qp2 objective sense substituting variables the substitute_variables method fixes specific variables to known values reducing the problem size this is useful for testing for warm starting or when you know part of the solution in advance from qiskit_optimization import quadraticprogram qp3 quadraticprogram substitution_demo qp3 binary_var x0 qp3 binary_var x1 qp3 binary_var x2 qp3 minimize linear x0 1 x1 2 x2 3 quadratic x0 x1 4 fix x0 1 leaving x1 and x2 free reduced qp3 substitute_variables constants x0 1 print original problem print qp3 export_as_lp_string print n after fixing x0 1 print reduced export_as_lp_string the objective becomes 1 2 x1 3 x2 4 1 x1 1 6 x1 3 x2 the constant 1 appears in the lp output as an offset worked example verifying the mathematical form consider a simple problem minimize x0 2 x1 subject to x0 x1 1 we encode it and verify from qiskit_optimization import quadraticprogram from qiskit_optimization converters import quadraticprogramtoqubo qp_verify quadraticprogram verify_example qp_verify binary_var x0 qp_verify binary_var x1 qp_verify minimize linear x0 1 x1 2 qp_verify linear_constraint linear x0 1 x1 1 sense rhs 1 name exactly_one print original lp print qp_verify export_as_lp_string convert to qubo and verify converter quadraticprogramtoqubo qubo converter convert qp_verify print n qubo form print qubo export_as_lp_string manually check for the constraint x0 x1 1 with penalty a the qubo objective should be x0 2 x1 a x0 x1 1 2 expanding x0 2 x1 a x0 2 x1 2 1 2 x0 x1 2 x0 2 x1 since x_i 2 x_i 1 2a a x0 2 2a a x1 2a x0 x1 a 1 a x0 2 a x1 2a x0 x1 a problem 1 max cut on a 5 node graph max cut asks partition graph nodes into two sets to maximize the number of edges that cross the partition boundary this maps naturally to binary variables which side each node is on import networkx as nx from qiskit_optimization import quadraticprogram from qiskit_optimization applications import maxcut build a random 5 node graph g nx gnm_random_graph 5 6 seed 42 the maxcut application class builds the quadraticprogram automatically maxcut maxcut g qp maxcut to_quadratic_program print qp export_as_lp_string convert to qubo and solve with qaoa from qiskit_optimization converters import quadraticprogramtoqubo from qiskit_optimization algorithms import minimumeigenoptimizer from qiskit_algorithms import qaoa from qiskit_algorithms optimizers import cobyla from qiskit primitives import sampler convert to qubo handles constraints via penalty terms automatically converter quadraticprogramtoqubo qubo converter convert qp set up qaoa with p 2 layers sampler sampler qaoa qaoa sampler sampler optimizer cobyla maxiter 200 reps 2 optimizer minimumeigenoptimizer qaoa result optimizer solve qp pass original qp not qubo print result print cut value maxcut interpret result minimumeigenoptimizer handles the qubo conversion internally the result object contains the binary assignment for each node and the objective value qubo conversion details the quadraticprogramtoqubo converter does several things behind the scenes understanding its internals helps you debug problems where the optimizer returns constraint violating solutions what the converter handles maximization to minimization if the original problem maximizes the converter negates all objective coefficients qubo is always a minimization problem linear constraints to quadratic penalties each equality constraint c t x b becomes a penalty term a c t x b 2 added to the objective each inequality constraint c t x b is first converted to an equality by introducing slack variables then penalized the same way slack variables for inequality constraints an inequality constraint like x0 x1 3 becomes x0 x1 s 3 where s is a new integer variable in 0 3 that gets binary encoded this adds ceil log2 4 2 extra binary variables to the problem inspecting penalty coefficients import networkx as nx from qiskit_optimization applications import maxcut from qiskit_optimization converters import quadraticprogramtoqubo g nx gnm_random_graph 5 6 seed 42 maxcut maxcut g qp maxcut to_quadratic_program convert with a specific penalty factor converter quadraticprogramtoqubo penalty 10 0 qubo converter convert qp compare the original and converted problems print f original variables qp get_num_vars print f qubo variables qubo get_num_vars print f penalty used converter penalty print print qubo objective lp form print qubo export_as_lp_string if you leave the penalty parameter as none the converter selects a penalty automatically based on the problem coefficients you can override it when the auto selected penalty is too small leading to constraint violations in the solution or too large creating numerical instability qubo expansion for the knapsack problem the knapsack problem has one inequality constraint total weight capacity which requires slack variables examine how the conversion expands the variable count from qiskit_optimization import quadraticprogram from qiskit_optimization converters import quadraticprogramtoqubo weights 2 3 4 5 1 values 3 4 5 7 2 capacity 8 qp_ks quadraticprogram knapsack_qubo_demo for i in range len weights qp_ks binary_var f x i qp_ks maximize linear f x i values i for i in range len values qp_ks linear_constraint linear f x i weights i for i in range len weights sense rhs capacity name weight_limit converter quadraticprogramtoqubo qubo_ks converter convert qp_ks print f original qp_ks get_num_vars variables f qp_ks get_num_linear_constraints constraints print f qubo qubo_ks get_num_vars variables f qubo_ks get_num_linear_constraints constraints print f n the slack variable encoding added f qubo_ks get_num_vars qp_ks get_num_vars extra binary variables the inequality x0 2 x1 3 x2 4 x3 5 x4 1 8 requires a slack variable s in 0 8 encoded with ceil log2 9 4 bits total 5 original 4 slack 9 qubo variables the original 5 variable knapsack problem becomes a 9 variable qubo after the slack variable encoding each additional qubit doubles the hilbert space so this expansion directly impacts the quantum resources required problem 2 0 1 knapsack the knapsack problem given items with weights and values choose which to pack to maximize total value without exceeding a weight capacity from qiskit_optimization import quadraticprogram from qiskit_optimization algorithms import minimumeigenoptimizer weights 2 3 4 5 1 values 3 4 5 7 2 capacity 8 qp quadraticprogram knapsack for i in range len weights qp binary_var f x i maximize total value qp maximize linear f x i values i for i in range len values weight constraint qp linear_constraint linear f x i weights i for i in range len weights sense rhs capacity name weight_limit solve with qaoa sampler sampler qaoa qaoa sampler sampler optimizer cobyla maxiter 300 reps 2 optimizer minimumeigenoptimizer qaoa result optimizer solve qp print result compare against brute force requires qiskit_optimization weights values result from above from itertools import product best_val best_combo 0 none for combo in product 0 1 repeat len weights total_weight sum w x for w x in zip weights combo total_value sum v x for v x in zip values combo if total_weight capacity and total_value best_val best_val best_combo total_value combo print f brute force optimal best_val items best_combo print f qaoa result result fval objective is stored as negated qaoa is a heuristic and does not guarantee the optimal solution especially at low circuit depth small reps increasing reps and maxiter improves approximation quality at the cost of longer runtime problem 3 traveling salesman 3 cities tsp asks for the shortest tour that visits every city exactly once the quadraticprogram formulation uses binary variables x_ i t 1 if city i is visited at time step t from qiskit_optimization applications import tsp import numpy as np distance matrix for 3 cities distances np array 0 10 15 10 0 12 15 12 0 tsp tsp distances qp_tsp tsp to_quadratic_program print f tsp with 3 cities qp_tsp get_num_binary_vars binary variables 3 cities 3 time steps 9 binary variables tsp scales quadratically in qubit count n cities need n 2 qubits for 5 cities you need 25 qubits which is already beyond what current nisq hardware can handle accurately with qaoa problem 4 vehicle routing the vehicle routing problem vrp generalizes tsp to multiple vehicles given n customers and k vehicles starting from a depot find routes for each vehicle so that every customer is visited exactly once and total travel distance is minimized binary variable encoding vrp uses binary variables x_ v i j 1 to indicate that vehicle v travels directly from location i to location j for n customers plus one depot n 1 locations and k vehicles the number of binary variables is k n 1 2 even a small instance grows quickly customers vehicles binary variables 3 1 16 4 2 50 6 2 98 10 3 363 solving vrp with qiskit import numpy as np from qiskit_optimization applications import vehiclerouting from qiskit_optimization algorithms import minimumeigenoptimizer from qiskit_algorithms import qaoa numpyminimumeigensolver from qiskit_algorithms optimizers import cobyla from qiskit primitives import sampler create a small vrp 3 customers 1 depot 2 vehicles the first node index 0 is the depot n_customers 3 n_vehicles 2 distance matrix depot 3 customers 4 locations distances np array 0 5 8 3 5 0 6 7 8 6 0 4 3 7 4 0 vrp vehiclerouting num_vehicles n_vehicles num_nodes n_customers 1 customers depot cost_matrix distances qp_vrp vrp to_quadratic_program print f vrp binary variables qp_vrp get_num_binary_vars print f vrp constraints qp_vrp get_num_linear_constraints solve exactly first feasible for small instances exact minimumeigenoptimizer numpyminimumeigensolver exact_result exact solve qp_vrp print f n exact result exact_result fval print f route assignment exact_result x the large variable count makes vrp one of the most resource hungry optimization problems for quantum approaches a 4 customer 2 vehicle vrp already requires more qubits than most nisq devices can handle with qaoa which is why vrp research focuses on decomposition strategies that break the problem into smaller subproblems qaoa circuit structure understanding the qaoa circuit helps you reason about circuit depth parameter counts and hardware requirements circuit components for a max cut problem with n nodes m edges and p layers the qaoa circuit consists of initialization n hadamard gates create an equal superposition of all 2 n bitstrings cost unitary repeated p times for each edge i j in the graph apply a zz interaction parameterized by gamma this is implemented as cnot rz cnot or equivalent decomposition the cost unitary encodes the max cut objective into the quantum state mixer unitary repeated p times apply rx 2 beta on every qubit the mixer drives transitions between bitstrings enabling the optimizer to explore the solution space measurement measure all qubits in the computational basis to obtain a candidate solution the circuit has 2p parameters total gamma_1 gamma_p and beta_1 beta_p finding the optimal values for these parameters is the classical optimization task explicit circuit for a 4 node ring graph p 1 import networkx as nx from qiskit_optimization applications import maxcut from qiskit_optimization converters import quadraticprogramtoqubo from qiskit_algorithms import qaoa from qiskit_algorithms optimizers import cobyla from qiskit primitives import sampler 4 node ring graph 0 1 2 3 0 g_ring nx cycle_graph 4 maxcut_ring maxcut g_ring qp_ring maxcut_ring to_quadratic_program build qaoa with p 1 sampler sampler qaoa_ring qaoa sampler sampler optimizer cobyla maxiter 100 reps 1 convert to operator to see the circuit converter quadraticprogramtoqubo qubo_ring converter convert qp_ring from qiskit_optimization translators import to_ising operator offset to_ising qubo_ring print ising hamiltonian print operator print f offset offset print f n circuit parameters 2 p 2 1 2 one gamma one beta print f qubits g_ring number_of_nodes print f zz interactions per layer g_ring number_of_edges one per edge print f rx gates per layer g_ring number_of_nodes one per qubit for the 4 node ring with 4 edges and p 1 each qaoa layer contains 4 zz interactions each decomposed into 2 cnots 1 rz and 4 rx gates the total circuit depth scales as o m p where m is the edge count parameter landscape visualization for p 1 qaoa has only two parameters gamma beta which makes it possible to visualize the full energy landscape as a 2d heatmap this visualization reveals the structure of the optimization problem and explains why some optimizer configurations converge better than others import numpy as np import networkx as nx import matplotlib pyplot as plt from qiskit_optimization applications import maxcut from qiskit_optimization converters import quadraticprogramtoqubo from qiskit_optimization translators import to_ising from qiskit_algorithms import qaoa from qiskit_algorithms optimizers import cobyla from qiskit primitives import sampler from qiskit quantum_info import sparsepauliop 4 node ring graph g_ring nx cycle_graph 4 maxcut_ring maxcut g_ring qp_ring maxcut_ring to_quadratic_program converter quadraticprogramtoqubo qubo_ring converter convert qp_ring operator offset to_ising qubo_ring scan over a 30x30 grid of gamma beta values n_points 30 gammas np linspace 0 2 np pi n_points betas np linspace 0 np pi n_points energy_grid np zeros n_points n_points sampler sampler for i gamma in enumerate gammas for j beta in enumerate betas build qaoa circuit with fixed parameters qaoa_eval qaoa sampler sampler optimizer cobyla maxiter 0 no optimization just evaluate reps 1 initial_point gamma beta evaluate the expectation value result qaoa_eval compute_minimum_eigenvalue operator energy_grid j i result eigenvalue real offset plot the energy landscape fig ax plt subplots 1 1 figsize 8 6 im ax pcolormesh gammas betas energy_grid shading auto cmap viridis ax set_xlabel r g amma ax set_ylabel r b eta ax set_title qaoa p 1 energy landscape 4 node ring max cut fig colorbar im ax ax label objective value mark the minimum min_idx np unravel_index np argmin energy_grid energy_grid shape ax plo...