Meta tags:
description=Implement the Bernstein-Vazirani algorithm in Qiskit: find a hidden bit string in a single query using superposition and phase kickback, versus N…;
author=QuantumComputingCourses.com;

Headings (most frequently used words):

the, oracle, quantum, step, to, why, algorithm, gf, hardware, dot, product, works, full, running, state, hadamard, bv, for, algorithms, with, bernstein, vazirani, string, in, qiskit, over, it, setup, building, second, analysis, connection, fourier, classical, vs, try, recursive, on, wrong, circuit, one, prepare, apply, transform, as, need, queries, example, kernel, ancilla, qubit, implementing, hidden, finder, problem, bitwise, and, linear, algebra, phase, kickback, derivation, amplitude, visualization, tracking, by, depth, scaling, verification, different, secrets, multi, query, noisy, real, adversarial, what, if, is, generalizing, relationship, machine, learning, common, mistakes, limitations, other, yourself, builder, related, tutorials, get, email, week, initial, after, layer, four, stages, verifying, statevector, simulator, walsh, big, picture, majority, voting, implementation, success, rate, table, structure, exponential, polynomial, significance, interpreting, results, perturbed, contrast, grover, encoding, simple, minimal, reversing, secret, lsb, msb, forgetting, measuring, confusing, mod, regular, only, shot, indices, ready, go, deeper, learn, reference, careers, about,

Text of the page (most frequently used words):
the (353), secret (125), oracle (98), for (88), and (74), #quantum (74), bit (52), algorithm (48), this (47), print (45), with (39), #ancilla (39), each (37), qubit (36), from (34), classical (34), string (32), range (32), state (31), circuit (31), you (31), queries (31), result (30), phase (27), quantumcircuit (27), counts (27), sqrt (27), hardware (26), qubits (26), level (25), query (24), that (24), one (23), import (23), hadamard (22), qiskit (22), return (22), all (21), has (21), wrong (20), over (20), product (20), xor (20), shots (20), def (20), input (20), depth (19), step (19), not (19), backend (19), int (19), bernstein (18), vazirani (18), error (18), 101 (18), 100 (18), basis (18), single (18), function (17), run (17), 10110 (17), real (16), fourier (16), transform (16), data (16), where (16), len (16), 354 (16), cnot (15), are (15), amplitude (14), full (14), dot (14), correct (14), str (14), exactly (14), needs (14), courses (13), why (13), kickback (13), gates (13), but (13), bits (13), aersimulator (13), σ_x (13), learning (12), read (12), more (12), superposition (12), 111 (12), kernel (12), 000 (12), position (12), probability (12), e_i (12), stage (12), guide (11), algorithms (11), linear (11), problem (11), maps (11), gives (11), measure (11), register (11), 011 (11), layer (11), apply (11), majority (11), tutorials (10), get (10), any (10), secrets (10), works (10), hidden (10), exponential (10), requires (10), key (10), get_counts (10), answer (10), results (10), reversed (10), total (10), measured (10), cnots (10), use (9), running (9), vector (9), instead (9), than (9), speedup (9), because (9), mod (9), into (9), noise (9), can (9), reveals (9), 010 (9), 001 (9), gate (9), after (9), count (9), what (8), min (8), recursive (8), different (8), second (8), bitwise (8), its (8), standard (8), which (8), when (8), shot (8), barrier (8), true (8), out (8), qc_bad (8), bernstein_vazirani (8), qiskit_aer (8), feature (8), compute (8), s_i (8), number (8), weight (8), analysis (7), measurement (7), uses (7), grover (7), structure (7), build (7), only (7), need (7), lsb (7), same (7), 110 (7), statevector (7), symbol (7), per (7), output (7), returns (7), bitstring (7), recovered (7), most_common (7), error_rate (7), applying (7), about (6), bloch (6), sphere (6), case (6), free (6), test (6), connection (6), common (6), machine (6), first (6), shor (6), bv_oracle (6), compose (6), max (6), simulator (6), strings (6), have (6), does (6), enumerate (6), through (6), trace (6), elements (6), two (6), errors (6), confidence (6), vote (6), rate (6), secret_bits (6), 2026 (5), how (5), setup (5), algebra (5), was (5), uniform (5), value (5), world (5), sum (5), addition (5), using (5), example (5), now (5), inplace (5), top (5), 1024 (5), style (5), map (5), inner (5), directly (5), field (5), hamming (5), 12s (5), noise_model (5), walsh (5), info (5), hamming_weight (5), policy (4), com (4), framework (4), learn (4), computing (4), time (4), other (4), relationship (4), noisy (4), try (4), scaling (4), building (4), derivation (4), these (4), simplest (4), find (4), advantage (4), take (4), most (4), show (4), measuring (4), stays (4), lambda (4), computes (4), prepare (4), reverse (4), many (4), simple (4), encoding (4), end (4), data_points (4), small (4), overlap (4), both (4), based (4), between (4), 02b (4), alpha (4), table (4), multiplication (4), polynomial (4), s_1 (4), robust (4), there (4), expected (4), put (4), implements (4), across (4), transpile (4), channel (4), success (4), 10000 (4), means (4), oracles (4), hides (4), they (4), oracle_fn (4), vectors (4), inverse (4), qc_stage_c (4), qc_stage_b (4), hello (4), your (3), track (3), see (3), our (3), amazon (3), editorial (3), job (3), careers (3), programming (3), glossary (3), studies (3), compare (3), independent (3), cirq (3), pennylane (3), series (3), ibm (3), related (3), python (3), beginner (3), limitations (3), mistakes (3), generalizing (3), adversarial (3), multi (3), verification (3), visualization (3), tracking (3), practical (3), browse (3), structured (3), needed (3), understand (3), three (3), qft (3), simon (3), direct (3), demonstrates (3), less (3), larger (3), problems (3), index (3), right (3), random (3), noiseless (3), always (3), 1000 (3), implement (3), integer (3), just (3), measures (3), information (3), while (3), items (3), without (3), must (3), character (3), msb (3), implementing (3), methods (3), here (3), mechanism (3), matrix (3), points (3), smaller (3), from_instruction (3), bv_feature_map (3), applies (3), numpy (3), sign (3), encodes (3), states (3), extract (3), appears (3), defined (3), gf4_multiply (3), element (3), still (3), since (3), interference (3), actually (3), intended (3), should (3), fidelity (3), 10100 (3), readout (3), current (3), flip (3), draw (3), ones (3), simply (3), 11111 (3), makes (3), version (3), levels (3), recover (3), then (3), own (3), 10s (3), majority_result (3), bit_votes (3), join (3), depolarizing_error (3), times (3), match (3), built (3), phases (3), given (3), giving (3), amplitudes (3), amp (3), qc_stage_d (3), copy (3), every (3), ψ_2 (3), e_1 (3), e_0 (3), classically (3), braket (3), cookies (2), affiliate (2), terms (2), llc (2), quantumcomputingcourses (2), books (2), podcasts (2), events (2), faq (2), company (2), jobs (2), interview (2), certifications (2), salary (2), timeline (2), types (2), docs (2), reference (2), news (2), frameworks (2), paths (2), references (2), tools (2), quantumcomputing (2), email (2), taking (2), changed (2), week (2), complete (2), course (2), ionq (2), reaching (2), point (2), bell (2), inequalities (2), chsh (2), know (2), entanglement (2), language (2), intermediate (2), guides (2), coursera (2), edx (2), udemy (2), brilliant (2), share (2), watch (2), probabilities (2), runs (2), entirely (2), builds (2), intuition (2), exact (2), quadratic (2), subgroup (2), best (2), practice (2), would (2), form (2), black (2), box (2), much (2), make (2), way (2), clear (2), mapping (2), also (2), above (2), composing (2), 4096 (2), might (2), give (2), least (2), good_classical_oracle (2), 03b (2), good (2), bad_classical_oracle (2), bad (2), zfill (2), bin (2), zip (2), regular (2), confusing (2), including (2), throughout (2), useful (2), sorted (2), prep (2), bv_no_ancilla_prep (2), produces (2), work (2), back (2), good_result (2), bad_result (2), qc_good (2), bad_oracle (2), highest (2), differ (2), values (2), quantum_kernel (2), abs (2), sv_x (2), sv_y (2), statevectors (2), phi (2), float (2), create (2), quantum_info (2), minimal (2), binary (2), inputs (2), fields (2), correction (2), gf4_trace (2), demonstrate (2), a_sq (2), represented (2), integers (2), insight (2), arithmetic (2), operations (2), individual (2), x_1 (2), s_2 (2), s_m (2), consider (2), them (2), multiple (2), amplifies (2), repeated (2), perturbation (2), corrupts (2), bv_with_custom_oracle (2), bv_oracle_perturbed (2), important (2), device (2), marker (2), else (2), sorted_counts (2), sampler (2), isa_qc (2), mode (2), samplerv2 (2), optimization_level (2), generate_preset_pass_manager (2), service (2), ibm_quantum_platform (2), qiskitruntimeservice (2), sections (2), final (2), getting (2), typically (2), benchmark (2), platforms (2), search (2), complexity (2), separation (2), versus (2), base (2), calls (2), solves (2), grows (2), exponentially (2), whose (2), o_1 (2), hiding (2), precisely (2), finds (2), original (2), even (2), depends (2), low (2), rates (2), voting (2), independently (2), majority_vote (2), bv_majority_vote (2), votes (2), counter (2), add_all_qubit_quantum_error (2), sq_error (2), cx_error (2), noisemodel (2), model (2), implementation (2), trials (2), test_secrets (2), 0000 (2), comparison (2), append (2), period (2), deterministic (2), χ_s (2), characters (2), group (2), functions (2), 11110 (2), 00000 (2), total_depth (2), num_cnots (2), analyze_oracle_depth (2), transpiled (2), zero (2), target (2), cannot (2), state_str (2), scale (2), factor (2), idx_anc0 (2), label (2), look (2), looking (2), onto (2), initial (2), let (2), unlike (2), again (2), five (2), e_2 (2), classical_bv_solver (2), classical_bv_oracle (2), solver (2), s_bits (2), s_0 (2), prerequisites (2), finder (2), wave (2), accept, decline, improve, experience, performance, cookie, privacy, disclosure, associate, earns, qualifying, purchases, contact, talent, pool, post, team, training, questions, cheatsheets, history, catalog, published, curated, anyone, 241, 220, 112, subscribe, address, new, worth, spam, unsubscribe, anytime, beginners, introduction, lecture, fundamentals, sept, updated, glance, page, next, bra, ket, notation, explained, previous, continue, ready, deeper, yes, tutorial, helpful, drop, pauli, update, instantly, browser, signup, install, open, screen, yourself, builder, instance, acting, cancellation, rather, amplification, replaces, achieving, possible, precursor, constructing, knowing, pedagogical, isolates, going, fold, improvement, dramatic, overhead, maintaining, computer, currently, sense, designed, shine, contrived, caveats, arise, reorder, non, layouts, composed, handles, correctly, sure, control, line, separate, method, double, check, indices, most_likely, sample, due, frequent, difference, pair, exceeds, computed, prone, strip, too, bv_measure_all, carry, unnecessary, break, already, factored, wastes, cause, confusion, reading, got, missing, leave, kick, forgetting, demonstration, bug, good_oracle, reversal, ordering, significant, corresponds, little, endian, reversing, pitfalls, tripped, people, experienced, programmers, tasks, expressive, shown, core, understanding, provides, conceptual, foundation, considers, similar, positions, exploits, repurposed, classification, dataset, squared, assert, component, showing, parameter, creates, similarity, encode, their, interfere, kernels, products, generalization, relevant, codes, querying, via, irreducible, multiply, consisting, generalized, whereas, decomposed, representation, consists, arranged, according, tables, represent, x_2, x_m, generalize, general, principle, average, maximally, sensitive, trades, robustness, efficiency, perturbations, marked, distribution, contrast, faithfully, reports, supposed, self, custom, mistake, suppose, meant, flipped, perturbed, assumes, perfectly, thought, experiment, something, fragility, poor, dominated, 10010, often, suggests, particular, higher, others, dominating, depending, remaining, spreads, especially, distance, tend, sort, isa, min_num_qubits, false, operational, least_busy, july, 2025, note, older, ibm_quantum, retired, transpiler, preset_passmanagers, qiskit_ibm_runtime, interpreting, separated, barriers, approximately, ignoring, interpretable, choosing, tunable, layers, easy, worrying, compilation, differences, fixed, well, shallow, limited, accumulate, serves, reasons, helped, motivate, natural, speedups, eventually, leading, construction, historically, provided, provable, separations, gap, significance, wait, careful, evaluate, evaluation, chains, down, involves, recursion, solve, those, solving, turn, tree, bottom, another, determined, nesting, continues, 1993, paper, went, further, stronger, provably, approach, extremely, moderate, far, worse, approximate, reliably, climbs, toward, remains, corrects, 005, correct_majority, correct_most_common, high, add, 10x, depolarizing, simulate, collections, application, hoeffding, inequality, exp, being, bounded, assuming, totally, broken, drops, perfect, suffices, conspire, fix, decoherence, matching, reads, 256, 01010101, 11001100, 10101010, 1111, set, probe, classical_bv, entire, family, starts, estimation, periodic, z_n, orthogonal, idea, scales, big, picture, pattern, pure, recovers, frequency, spectral, approximation, uncertainty, leakage, involution, twice, delta, peaked, becomes, g_hat, written, decomposes, coefficients, under, beautiful, interpretation, lens, linearly, lower, produce, cleaner, fewer, accumulated, basis_gates, analyze, dict, circuits, shallower, resistant, zeros, trivially, worst, parallel, execute, sequentially, therefore, equally, deep, setting, underlies, signal, processing, qpe, inverts, returning, sum_x, code, tracks, actual, numerical, confirming, hand, calculations, format, branch, array, list, qargs, probs, alternatively, multiplying, 2nd, tracing, verifying, certainty, constructive, destructive, collapse, magnitudes, equal, encoded, signs, sits, four, stages, complex, concrete, probabilistic, repetition, close, decode, computational, initialise, adds, acts, qubit_i, yields, randomness, ψ_3, prove, applied, identity, factors, focusing, change, kicks, cases, ψ_1, combined, ψ_0, start, walk, mathematical, done, thing, simultaneously, e_4, e_3, 01000, 00100, 00010, 00001, verify, equals, takes, strategy, combination, include, some, term, except, happens, everywhere, x_0, necessary, sufficient, behind, finite, enough, mechanically, unknown, access, cleanest, demonstrations, hard, delivers, clean, diagram, physics, background, basic, variables, loops, jan, concepts, home, troubleshooting, universities, career, cheat, sheets, migration, pinball, explore, ocean, tket, pyquil, rigetti, quera, azure, quantinuum, google, providers, skip, main, content,

Text of the page (random words):
the probability that the majority vote across n trials is wrong is bounded by p error exp 2n 0 5 e 2 this is a direct application of the hoeffding inequality implementation from qiskit import quantumcircuit from qiskit_aer import aersimulator from qiskit_aer noise import noisemodel depolarizing_error from collections import counter def bv_majority_vote secret str shots int 100 error_rate float 0 01 run bv multiple times and take majority vote per bit position uses a noise model to simulate real hardware n len secret create a simple noise model depolarizing error on cx gates noise_model noisemodel cx_error depolarizing_error error_rate 2 noise_model add_all_qubit_quantum_error cx_error cx also add single qubit gate error typically 10x smaller sq_error depolarizing_error error_rate 10 1 noise_model add_all_qubit_quantum_error sq_error h x backend aersimulator noise_model noise_model qc bernstein_vazirani secret run with many shots counts backend run qc shots shots result get_counts majority vote find the most common result most_common max counts key counts get confidence counts most_common shots per bit majority vote more robust for high noise bit_votes counter for _ in range n for bitstring count in counts items for i bit in enumerate bitstring bit_votes i bit count majority_result join votes most_common 1 0 0 for votes in bit_votes return most_common most_common majority_vote majority_result confidence confidence correct_most_common most_common secret correct_majority majority_result secret test with different error rates secret 10110 print f secret secret print f error rate 12s most common 12s majority 10s confidence 10s print 55 for error_rate in 0 001 0 005 0 01 0 02 0 05 0 10 result bv_majority_vote secret shots 1000 error_rate error_rate print f error_rate 12 3f result most_common 12s f result majority_vote 10s result confidence 10 1 at low error rates 0 1 to 1 both methods recover the correct string reliably as the error rate climbs toward 5 to 10 per bit majority voting remains more robust than simply taking the single most common bitstring because it independently corrects each bit position success rate table for a 5 bit secret with 3 cnots the approximate success probability per shot depends on the two qubit gate error rate cx error rate p correct per shot p correct 100 shot majority 0 1 99 7 99 99 0 5 98 5 99 99 1 97 0 99 99 2 94 1 99 9 5 85 7 99 10 72 9 95 the majority vote approach makes bv extremely robust to moderate noise levels even with 10 cx error far worse than current hardware 100 shots give about 95 success recursive bernstein vazirani the standard bv algorithm finds a hidden string in one query but bernstein and vazirani s original 1993 paper went further they defined a recursive version that demonstrates an even stronger quantum advantage a separation between quantum and classical query complexity that is provably exponential the recursive oracle structure in the recursive version you have a tree of oracles at the bottom level level 0 there are many bv oracles each hiding its own secret string s_i at level 1 another bv oracle hides a string whose bits are determined by the secrets recovered from level 0 this nesting continues for d levels more precisely level 0 you have 2 n independent bv oracles o_ 0 1 o_ 0 2 each hiding a secret s_ 0 i level 1 a bv oracle o_1 where the j th query to o_1 requires you to first recover the secret s_ 0 j from a level 0 oracle then use that secret to compute the j th bit of the level 1 answer level d the top level oracle whose secret is the final answer why classical algorithms need exponential queries a classical algorithm at level d needs n queries to solve the top level bv problem but each of those n queries requires solving a level d 1 bv problem which in turn requires n queries at level d 2 and so on the total number of classical queries is classical queries n d this grows exponentially with the recursion depth d why quantum algorithms need polynomial queries a quantum algorithm at each level solves bv in 1 query but that single query involves running a level d 1 quantum bv circuit the total number of oracle calls at the base level is quantum queries n d wait we need to be more careful at each level a single quantum query to the level k oracle requires running the level k 1 circuit in superposition the total number of base level oracle calls is actually n for each level you need to evaluate the oracle on a superposition of inputs but each evaluation chains down to level 0 the total is quantum queries at level 0 o n d this gives a separation of n d classical versus o n d quantum which is exponential in d significance this recursive construction was historically important because it provided one of the first provable exponential separations between quantum and classical query complexity while the standard bv problem has only a linear speedup n queries to 1 the recursive version amplifies this into an exponential gap by composing the linear advantage across d levels this result helped motivate the search for more natural problems with exponential quantum speedups eventually leading to simon s algorithm and shor s algorithm running on real hardware on real ibm quantum hardware the algorithm still works well because the circuit is shallow only k cnot gates for a secret with hamming weight k which means noise has limited time to accumulate bv serves as a useful hardware benchmark for three reasons a fixed circuit depth the circuit has exactly 3 layers of gates h layer oracle cnots h layer this makes it easy to compare across hardware platforms without worrying about compilation differences b tunable cnot count the number of cnots is exactly the hamming weight of s you can test hardware at different cnot counts simply by choosing different secrets from 1 cnot s 10000 up to n cnots s 11111 c success probability directly measures fidelity if the hardware has cx fidelity f per gate and the secret has k ones the probability of getting the correct answer is approximately f k ignoring single qubit errors and readout errors which are typically smaller this gives a direct interpretable benchmark number full circuit for n 5 secret 10110 n len secret qc bernstein_vazirani secret print full bv circuit for s 10110 print qc draw the circuit has 5 input qubits 1 ancilla and 5 classical bits you can see three clear sections separated by barriers the h layer the 3 cnot gates for bits 1 2 4 where s has 1s and the final h layer interpreting hardware results from qiskit_ibm_runtime import qiskitruntimeservice samplerv2 from qiskit transpiler preset_passmanagers import generate_preset_pass_manager note older docs show channel ibm_quantum that channel was retired in july 2025 use the current ibm_quantum_platform channel instead service qiskitruntimeservice channel ibm_quantum_platform backend service least_busy operational true simulator false min_num_qubits 6 secret 10110 qc bernstein_vazirani secret transpile to isa circuit pm generate_preset_pass_manager backend backend optimization_level 1 isa_qc pm run qc sampler samplerv2 mode backend result sampler run isa_qc shots 4096 result counts result 0 data c get_counts sort by count show top 5 results sorted_counts sorted counts items key lambda x x 1 reverse true total sum counts values print f secret secret print f n top 5 results out of total shots for bitstring count in sorted_counts 5 marker correct if bitstring secret else print f bitstring count 4d count total 1 marker on current hardware you should see the correct answer 10110 dominating with 70 to 90 of the shots depending on the device the remaining probability spreads across other strings especially strings that differ from 10110 by one bit hamming distance 1 this is because single gate errors tend to flip individual qubits if the correct answer appears in less than 50 of shots the device has poor fidelity for this circuit depth if the error is dominated by a single qubit e g 10010 appears much more often than 10100 that suggests one particular cx gate or qubit readout has higher error than the others adversarial oracle what if the oracle is wrong the bv algorithm assumes the oracle perfectly implements f x s x but what if the oracle has an error this thought experiment reveals something important about bv s fragility a perturbed oracle suppose the oracle is meant to implement s 101 on 3 qubits but one cnot is flipped instead of cnots on qubits 0 and 2 the oracle has cnots on qubits 0 and 1 this implements f x s x where s 011 instead of s 101 from qiskit import quantumcircuit from qiskit_aer import aersimulator def bv_oracle_perturbed n int quantumcircuit oracle intended for s 101 but with a mistake cnot on qubit 1 instead of qubit 2 actually implements s 011 qc quantumcircuit n 1 qc cx 0 n correct qubit 0 for the 1 in position 2 lsb qc cx 1 n wrong should be qubit 2 but we put qubit 1 return qc def bv_with_custom_oracle oracle quantumcircuit n int quantumcircuit build bv circuit with a custom oracle qc quantumcircuit n 1 n qc x n qc h n qc h range n qc barrier qc compose oracle inplace true qc barrier qc h range n qc measure range n range n return qc n 3 oracle bv_oracle_perturbed n qc bv_with_custom_oracle oracle n backend aersimulator counts backend run qc shots 1024 result get_counts print f intended secret 101 print f measured result max counts key counts get print f counts counts expected output intended secret 101 measured result 011 counts 011 1024 bv faithfully reports what the oracle actually computes not what it was supposed to compute if the oracle is wrong bv returns the wrong answer with 100 confidence there is no self correction mechanism contrast with grover s algorithm grover s algorithm is more robust to small oracle perturbations because grover uses multiple queries about sqrt n of them and amplifies the marked state through repeated interference a small perturbation in the oracle results in a small perturbation in the output distribution bv uses exactly one query so any oracle error directly corrupts the result this is a general principle algorithms that use more queries can average over oracle errors while single query algorithms are maximally sensitive to them bv trades robustness for efficiency generalizing to gf 2 k the standard bv algorithm works over gf 2 the field with two elements each symbol in the secret string is a single bit we can generalize to larger fields gf 2 k where each symbol is a k bit string and field operations are defined by polynomial arithmetic the setup instead of an n bit secret string over gf 2 consider an m symbol secret string over gf 2 k s s_1 s_2 s_m where each s_i is in gf 2 k the function to learn is f x s_1 x_1 s_2 x_2 s_m x_m over gf 2 k where and are field multiplication and addition in gf 2 k quantum encoding each symbol s_i requires k qubits to represent so the total number of qubits for the input register is m k the oracle applies a phase based on the gf 2 k inner product the key insight since gf 2 k arithmetic can be decomposed into operations on k individual bits using the polynomial representation of the field the oracle circuit consists of cnot gates arranged according to the multiplication tables of gf 2 k a simple example gf 4 gf 4 gf 2 2 has elements 0 1 α α 1 where α 2 α 1 0 each element is represented by 2 bits 0 00 1 01 α 10 α 1 11 for a secret consisting of a single gf 4 symbol you need 2 qubits per register position a single quantum query to the generalized bv oracle reveals the 2 bit symbol whereas a classical algorithm over gf 4 still requires standard basis queries from qiskit import quantumcircuit from qiskit_aer import aersimulator def gf4_multiply a int b int int multiply two elements of gf 4 gf 2 2 elements represented as 2 bit integers irreducible polynomial x 2 x 1 if a 0 or b 0 return 0 gf 4 multiplication table elements 0 00 1 01 alpha 10 alpha 1 11 table 1 1 1 1 2 2 1 3 3 2 1 2 2 2 3 2 3 1 3 1 3 3 2 1 3 3 2 return table get a b 0 def gf4_trace a int int trace function from gf 4 to gf 2 tr a a a 2 in gf 4 this maps gf 4 to 0 1 a_sq gf4_multiply a a return a a_sq xor is addition in gf 2 k demonstrate for secret symbol s alpha 10 show that querying on each basis element reveals the secret via the trace secret 2 alpha 10 in binary print f secret secret secret 02b for x in range 4 product gf4_multiply secret x trace gf4_trace product print f f x 02b tr s x 02b tr product 02b trace this generalization is relevant to quantum linear algebra algorithms and quantum error correction codes defined over larger fields relationship to quantum machine learning the bv algorithm s structure prepare a superposition apply an oracle interfere to extract information appears throughout quantum machine learning the phase kickback mechanism is directly related to how quantum kernels compute inner products bv as a quantum kernel in classical machine learning a kernel function k x y measures similarity between data points in quantum kernel methods you encode classical data into quantum states and measure their overlap the bv oracle for secret s creates the mapping x 1 s x this is a binary feature map it maps each n bit string x to a sign based on its inner product with s the quantum state after the oracle 1 sqrt 2 n σ_x 1 s x x is a feature state that encodes the relationship between all inputs x and the hidden parameter s a minimal quantum kernel example here is a minimal example showing how a bv style circuit computes a quantum kernel value from qiskit import quantumcircuit from qiskit quantum_info import statevector import numpy as np def bv_feature_map data str n int quantumcircuit create a bv style feature map circuit maps classical data string to a quantum state using phase kickback qc quantumcircuit n hadamard layer qc h range n phase encoding based on data for i bit in enumerate reversed data if bit 1 qc z i z gate applies 1 phase to 1 component second hadamard layer qc h range n return qc def quantum_kernel x str y str float compute quantum kernel value phi x phi y 2 using bv style feature maps n len x assert len y n get statevectors for both feature maps sv_x statevector from_instruction bv_feature_map x n sv_y statevector from_instruction bv_feature_map y n kernel value is the squared overlap overlap np abs sv_x inner sv_y 2 return overlap compute kernel matrix for a small dataset data_points 000 001 010 011 100 101 110 111 n 3 print quantum kernel matrix bv style feature map print f 4s end for y in data_points print f y 5s end print for x in data_points print f x 4s end for y in data_points k quantum_kernel x y print f k 5 2f end print the kernel matrix reveals which data points the bv feature map considers similar points that differ in more bit positions have smaller kernel values this is the same inner product structure that bv exploits now repurposed for classification in practice quantum kernel methods for real machine learning tasks use more expressive feature maps than the simple bv style map sho...