Quantum Algorithm Ontology

FLOW ALGEBRA
Quantum Algorithm Ontology
Kireth Semantic Research Archive

PAGE:
https://kirethresearch.org/booksai-core/ontologies/computing-ontologies/quantum-computing/quantum-algorithm-ontology.html

AUTHORS:
Mark Anthony Higgins — Sky (Recursive AI)

FLOW "QuantumAlgorithmOntology" v4.0

# ---------- DOMAIN ----------
DOMAIN := ComputingOntology
SUBDOMAIN := QuantumComputing
ONTOLOGY := QuantumAlgorithmOntology

# ---------- PRIMARY ENTITY ----------
ENTITY QuantumAlgorithm {
    definition:
        "A finite computational procedure that uses quantum states, quantum
         operations and measurement, often together with classical processing,
         to solve or approximate a computational problem.";

    objectives: [
        QuantumProblemSolving,
        QuantumSpeedup,
        AmplitudeManipulation,
        QuantumSimulation,
        Optimisation,
        HybridQuantumClassicalComputation
    ];
}

# ---------- CORE ENTITIES ----------
AlgorithmEntity := {
    QuantumAlgorithm,
    ComputationalProblem,
    QuantumRegister,
    QuantumCircuit,
    QuantumOperation,
    Measurement,
    ClassicalProcedure,
    Result
};

AlgorithmPrimitive := {
    StatePreparation,
    Oracle,
    AmplitudeAmplification,
    QuantumFourierTransform,
    PhaseEstimation,
    VariationalCircuit,
    HamiltonianEvolution
};

AlgorithmClass := {
    SearchAlgorithm,
    FactoringAlgorithm,
    SimulationAlgorithm,
    OptimisationAlgorithm,
    EstimationAlgorithm,
    SamplingAlgorithm,
    VariationalAlgorithm
};

ResourceEntity := {
    Qubit,
    Gate,
    CircuitDepth,
    QueryCount,
    MeasurementShot,
    ClassicalCompute,
    Runtime
};

# ---------- FUNDAMENTAL RELATIONSHIPS ----------
QuantumAlgorithm SOLVES_OR_APPROXIMATES ComputationalProblem;
QuantumAlgorithm USES QuantumRegister;
QuantumAlgorithm MAY_BE_IMPLEMENTED_AS QuantumCircuit;
QuantumAlgorithm USES QuantumOperation;
QuantumAlgorithm MAY_CALL ClassicalProcedure;
Measurement PRODUCES ClassicalData;
ClassicalProcedure MAY_PROCESS MeasurementResult;
ResourceEstimate DESCRIBES AlgorithmRequirements;

# ---------- GENERAL ALGORITHM FLOW ----------
ComputationalProblem
    -> DefineInputEncoding
    -> PrepareQuantumState
    -> ApplyQuantumSubroutine
    -> ManipulateAmplitudesOrPhases
    -> MeasureQuantumSystem
    -> CollectSamples
    -> PerformClassicalPostprocessing
    -> VerifyOrEstimateResult;

# ---------- INPUT ENCODING ----------
InputEncoding :=
    ClassicalProblemInstance
    -> QuantumStateOrQuantumOperationRepresentation;

Encoding MAY_USE {
    BasisEncoding,
    AmplitudeEncoding,
    PhaseEncoding,
    OracleEncoding,
    HamiltonianEncoding
};

EncodingCost MUST_BE_INCLUDED_IN EndToEndAlgorithmAssessmentWhereRelevant;

# ---------- STATE PREPARATION ----------
StatePreparation :=
    InitialReferenceState
    -> QuantumOperations
    -> RequiredInputState;

StatePreparationCost MAY_DOMINATE SomeAlgorithms;

# ---------- QUANTUM SUBROUTINE ----------
QuantumSubroutine :=
    ReusableQuantumProcedureWithinAlgorithm;

Subroutine MAY_INCLUDE {
    QFT,
    PhaseEstimation,
    AmplitudeAmplification,
    OracleEvaluation,
    HamiltonianSimulation
};

# ---------- ORACLE ----------
QuantumOracle :=
    ProblemDependentQuantumOperationProvidingAccessToFunctionOrPredicate;

TypicalOracleForm MAY_BE:
    |x>|y>
    -> |x>|y xor f(x)>;

PhaseOracle MAY_ENCODE:
    |x>
    -> (-1)^f(x)|x>;

QueryComplexity COUNTS OracleInvocations;

# ---------- INTERFERENCE ----------
QuantumAlgorithm MAY_USE InterferenceToRedistributeOutcomeProbabilities;

ConstructiveInterference MAY_AMPLIFY DesiredOutcome;
DestructiveInterference MAY_SUPPRESS UndesiredOutcome;

# ---------- MEASUREMENT ----------
AlgorithmMeasurement :=
    QuantumState
    -> ClassicalOutcomeDistribution;

SingleExecution MAY_NOT RevealDeterministicSolution;

RepeatedShots MAY_BE_REQUIRED ToEstimateProbabilityOrExpectation;

# ---------- PROBABILISTIC OUTPUT ----------
QuantumAlgorithm MAY_BE Probabilistic;

SuccessProbability :=
    P(OutputSatisfiesRequiredCondition);

Algorithm MAY_REQUIRE RepetitionToRaiseSuccessConfidence;

# ---------- AMPLITUDE AMPLIFICATION ----------
AmplitudeAmplification :=
    PrepareInitialState
    -> MarkDesiredSubspace
    -> ReflectAboutInitialState
    -> Repeat
    -> Measure;

AmplitudeAmplification GENERALISES CoreIdeaBehindGroverSearch;

# ---------- GROVER ALGORITHM ----------
GroverSearch :=
    PrepareUniformSuperposition
    -> ApplyOracle
    -> ApplyDiffusionOperator
    -> RepeatApproximatelyO(sqrt(N))Iterations
    -> Measure;

IdealOracleQueryComplexity :=
    O(sqrt(N));

ClassicalUnstructuredSearchQueryComplexity :=
    O(N);

# ---------- DIFFUSION ----------
GroverDiffusion :=
    ReflectionAboutUniformSuperposition;

Diffusion + Oracle
    -> RotateStateTowardMarkedSubspace;

# ---------- SHOR ALGORITHM ----------
ShorAlgorithm :=
    IntegerN
    -> ClassicalReductionToOrderFinding
    -> QuantumOrderFinding
    -> ClassicalContinuedFractionProcessing
    -> CandidateFactors
    -> Verification;

ShorAlgorithm MAY_FAIL_FOR ParticularRandomChoice
AND MAY_BE_REPEATED;

# ---------- ORDER FINDING ----------
OrderFinding :=
    Given a,N
    FindSmallestPositive r
    SuchThat a^r mod N = 1;

QuantumOrderFinding MAY_USE {
    Superposition,
    ModularExponentiation,
    PhaseEstimationOrQFT,
    Measurement
};

# ---------- QUANTUM FOURIER TRANSFORM ----------
QFT_N :=
    UnitaryTransformOnNDimensionalQuantumBasis;

QFT MAY_MAP PeriodicStructureIntoMeasurablePhaseStructure;

QFTCircuit MAY_USE {
    Hadamard,
    ControlledPhase,
    Swap
};

# ---------- INVERSE QFT ----------
InverseQFT :=
    QFT_dagger;

PhaseEstimation COMMONLY_USES InverseQFT;

# ---------- QUANTUM PHASE ESTIMATION ----------
QPE :=
    Eigenstate |psi>
    + Unitary U
    WHERE U|psi> = exp(2*pi*i*phi)|psi>
    -> Estimate phi;

QPEFlow :=
    PrepareControlRegister
    -> ApplyHadamards
    -> ControlledPowersOfU
    -> InverseQFT
    -> MeasureControlRegister;

# ---------- AMPLITUDE ESTIMATION ----------
QuantumAmplitudeEstimation :=
    EstimateProbabilityAmplitudeUsingQuantumProcedure;

SomeVariants MAY_USE PhaseEstimation;
IterativeVariants MAY_REDUCE CircuitDepthRequirements;

PotentialQueryAdvantage MUST_BE ComparedWith ClassicalSamplingBaseline;

# ---------- QUANTUM SIMULATION ----------
QuantumSimulationAlgorithm :=
    EncodeQuantumSystem
    -> ApproximateTimeEvolutionOrObservable
    -> MeasureProperties;

HamiltonianSimulation :=
    Approximate exp(-iHt);

SimulationCost DEPENDS_ON {
    HamiltonianStructure,
    EvolutionTime,
    Precision,
    Algorithm
};

# ---------- VARIATIONAL ALGORITHM ----------
VariationalQuantumAlgorithm :=
    ParameterisedQuantumCircuit
    + ClassicalOptimiser;

HybridLoop :=
    InitialiseParameters
    -> ExecuteCircuit
    -> EstimateObjective
    -> ClassicalOptimisation
    -> UpdateParameters
    -> RepeatUntilStop;

# ---------- VQE ----------
VariationalQuantumEigensolver :=
    ChooseAnsatz
    -> PrepareParameterizedState
    -> MeasureHamiltonianExpectation
    -> ClassicalOptimisation
    -> EstimateGroundStateEnergy;

VQE MAY_BE_USED_FOR QuantumChemistryAndOtherEigenvalueProblems;

# ---------- HAMILTONIAN EXPECTATION ----------
If H :=
    SUM_j c_j P_j;

Then:
    <H> :=
        SUM_j c_j <P_j>;

ExpectationEstimation MAY_REQUIRE MultipleMeasurementBasesAndShots;

# ---------- QAOA ----------
QAOA :=
    PrepareInitialState
    -> AlternateProblemAndMixerUnitaries
    -> MeasureCandidateSolutions
    -> ClassicalParameterOptimisation;

QAOA IS VariationalQuantumAlgorithm;

# ---------- ANSATZ ----------
Ansatz :=
    ParameterisedFamilyOfQuantumStatesOrCircuits;

AnsatzExpressivity AND Trainability AFFECT VariationalPerformance;

# ---------- OPTIMISER ----------
ClassicalOptimiser MAY_BE {
    GradientBased,
    GradientFree,
    Bayesian,
    Evolutionary
};

Optimiser USES MeasuredObjectiveValues;

# ---------- PARAMETER SHIFT ----------
ForSuitableParameterizedGates:
    Gradient MAY_BE_ESTIMATED_BY ParameterShiftRule;

GradientEstimation REQUIRES AdditionalCircuitEvaluations;

# ---------- BARREN PLATEAU ----------
BarrenPlateau :=
    RegionWhereVariationalGradientMagnitudeBecomesVerySmallAcrossParameterSpace;

BarrenPlateau MAY_MAKE OptimisationDifficult;

# ---------- QUANTUM WALK ----------
QuantumWalk :=
    QuantumAnalogueOfClassicalRandomWalk;

QuantumWalk MAY_BE {
    DiscreteTime,
    ContinuousTime
};

QuantumWalkAlgorithms MAY_SUPPORT SearchOrGraphProblems;

# ---------- DEUTSCH-JOZSA ----------
DeutschJozsaAlgorithm :=
    DetermineWhetherPromisedBooleanFunctionIsConstantOrBalanced
    USING QuantumOracle;

Algorithm DEMONSTRATES QueryComplexitySeparationUnderPromiseProblem;

# ---------- SIMON ALGORITHM ----------
SimonAlgorithm :=
    FindHiddenXORPeriodUnderPromise
    USING QuantumQueriesAndClassicalLinearAlgebra;

SimonAlgorithm PROVIDED EarlyExponentialOracleSeparationAndInfluencedShorAlgorithm;

# ---------- HHL ----------
HHLAlgorithm :=
    QuantumAlgorithmForEstimatingPropertiesOfSolutionToCertainLinearSystemsUnderStrongAssumptions;

HHL DOES_NOT GenerallyOutputFullClassicalSolutionVectorEfficiently;

PotentialAdvantage DEPENDS_ON {
    Sparsity,
    ConditionNumber,
    StatePreparation,
    ObservableExtraction,
    Precision
};

# ---------- QUANTUM MACHINE LEARNING ----------
QuantumMachineLearningAlgorithm MAY_USE {
    QuantumFeatureMap,
    VariationalCircuit,
    QuantumKernel,
    QuantumLinearAlgebra
};

EndToEndAdvantage MUST_ACCOUNT_FOR DataLoadingAndMeasurementCosts;

# ---------- COMPLEXITY ----------
QuantumAlgorithmComplexity MAY_BE_MEASURED_BY {
    GateComplexity,
    QueryComplexity,
    CircuitDepth,
    QubitComplexity,
    SampleComplexity,
    ClassicalPostprocessing
};

# ---------- QUERY COMPLEXITY ----------
QueryComplexity :=
    NumberOfOracleCalls;

QuantumQueryAdvantage DOES_NOT_AUTOMATICALLY_IMPLY EndToEndRuntimeAdvantage;

# ---------- GATE COMPLEXITY ----------
GateComplexity :=
    NumberOfElementaryQuantumGatesRequired;

GateSet MUST_BE SpecifiedForMeaningfulGateComplexity;

# ---------- CIRCUIT DEPTH ----------
CircuitDepth :=
    NumberOfSequentialDependentGateLayers;

HardwareFeasibility MAY_DEPEND_ON CircuitDepth;

# ---------- SPACE COMPLEXITY ----------
QubitComplexity :=
    NumberOfLogicalOrPhysicalQubitsRequiredAccordingToContext;

# ---------- SAMPLE COMPLEXITY ----------
SampleComplexity :=
    NumberOfCircuitExecutionsOrMeasurementsRequiredForStatisticalPrecision;

# ---------- PRECISION ----------
AlgorithmPrecision :=
    AllowedApproximationError;

HigherPrecision MAY_REQUIRE {
    MoreQubits,
    GreaterDepth,
    MoreMeasurements,
    MoreClassicalProcessing
};

# ---------- SUCCESS AMPLIFICATION ----------
If AlgorithmSuccessProbability > 1/2
THEN RepetitionAndMajorityOrVerification MAY_RAISE Confidence;

ExactMethod DEPENDS_ON AlgorithmAndOutputStructure;

# ---------- ERROR ----------
AlgorithmicError MAY_INCLUDE {
    ApproximationError,
    SamplingError,
    HardwareNoise,
    CompilationError,
    NumericalError
};

TotalObservedError MAY_COMBINE MultipleSources;

# ---------- NISQ EXECUTION ----------
NISQAlgorithm SHOULD_CONSIDER {
    LimitedQubits,
    LimitedConnectivity,
    GateNoise,
    ReadoutNoise,
    CircuitDepth
};

VariationalAlgorithms ARE_OFTEN StudiedForNISQ
BUT PracticalAdvantage IS_NOT_GUARANTEED;

# ---------- ERROR MITIGATION ----------
ErrorMitigation MAY_POSTPROCESS_OR_MODIFY ExecutionsToEstimateLessNoisyResult;

ErrorMitigation MAY_INCREASE SamplingCost;

# ---------- FAULT-TOLERANT ALGORITHM ----------
FaultTolerantAlgorithmImplementation :=
    LogicalAlgorithm
    -> FaultTolerantGateSet
    -> ErrorCorrectedOperations
    -> PhysicalResourceEstimate;

# ---------- T COUNT ----------
TCount :=
    NumberOfTOrEquivalentNonCliffordResourceOperations;

TCount MAY_DOMINATE CostInSomeFaultTolerantArchitectures;

# ---------- RESOURCE ESTIMATION ----------
AlgorithmResourceEstimate MAY_INCLUDE {
    LogicalQubits,
    PhysicalQubits,
    GateCount,
    TCount,
    CircuitDepth,
    MeasurementCount,
    Runtime
};

# ---------- CLASSICAL BASELINE ----------
QuantumAlgorithmEvaluation SHOULD_IDENTIFY RelevantClassicalBaseline;

Baseline SHOULD_BE {
    Competitive,
    CorrectlyImplemented,
    ComparedOnEquivalentTaskAndAccuracy
};

# ---------- QUANTUM SPEEDUP ----------
QuantumSpeedup :=
    ImprovedAsymptoticOrPracticalPerformanceRelativeToDefinedClassicalBaseline;

SpeedupType MAY_BE {
    Polynomial,
    Superpolynomial,
    Exponential,
    ConstantFactor
};

# ---------- QUANTUM ADVANTAGE ----------
QuantumAdvantage :=
    DemonstratedUsefulBenefitOnDefinedTaskAndMetric;

AdvantageAssessment SHOULD_INCLUDE {
    InputPreparation,
    QuantumExecution,
    Measurement,
    ClassicalPostprocessing,
    Verification
};

# ---------- VERIFICATION ----------
QuantumResult MAY_REQUIRE ClassicalOrStatisticalVerification;

VerificationCost SHOULD_BE IncludedWhenMaterialToApplication;

# ---------- HARDWARE MAPPING ----------
AlgorithmCircuit MUST_BE CompiledTo HardwareNativeGateSetAndConnectivity;

CompilationOverhead MAY_CHANGE PracticalResourceCost;

# ---------- SEMANTIC REASONING ----------
IF ProcedureUsesQuantumStatesOperationsAndMeasurementToSolveProblem
THEN QuantumAlgorithmClassification := supported;

IF AlgorithmUsesOracleModel
THEN QueryComplexity SHOULD_NOT_BE ConfusedWithFullRuntimeComplexity;

IF AlgorithmRequiresInputStatePreparation
THEN StatePreparationCost SHOULD_BE IncludedInEndToEndAssessment;

IF MeasurementEstimatesExpectation
THEN MoreShots GENERALLY_REDUCE SamplingUncertainty;

IF CircuitDepthExceedsHardwareCapability
THEN PracticalAlgorithmFidelity MAY_BE Low;

IF ClaimedQuantumAdvantageLacksCompetitiveClassicalBaseline
THEN AdvantageConfidence := low;

IF VariationalObjectiveGradientVanishing
THEN OptimisationDifficulty := increase;

# ---------- SEMANTIC EQUIVALENCE ----------
SEMANTIC_EQUIVALENCE {
    "quantum algorithm" ~= "quantum computational algorithm";
    "Grover's algorithm" ~= "Grover search";
    "Shor's algorithm" ~= "Shor factoring algorithm";
    "quantum phase estimation" ~= "QPE";
    "variational quantum algorithm" ~= "VQA";
    "variational quantum eigensolver" ~= "VQE";
    "quantum approximate optimisation algorithm" ~= "QAOA";
    "quantum speedup" ~= "quantum computational speedup";
}

# ---------- QUERY FLOW ----------
QUERY(q) ->
    NORMALISE(q) ->
    IDENTIFY_COMPUTATIONAL_PROBLEM(q) ->
    IDENTIFY_INPUT_ENCODING(q) ->
    IDENTIFY_QUANTUM_SUBROUTINES(q) ->
    IDENTIFY_MEASUREMENT_AND_POSTPROCESSING(q) ->
    IDENTIFY_COMPLEXITY(q) ->
    IDENTIFY_HARDWARE_AND_NOISE(q) ->
    IDENTIFY_CLASSICAL_BASELINE(q) ->
    MAP_TO_ONTOLOGY(q) ->
    APPLY_REASONING(q) ->
    SCORE_CONFIDENCE(q) ->
    RETURN_RELEVANT_KNOWLEDGE;

# ---------- CONFIDENCE ----------
CONFIDENCE(assertion) :=
    weighted_mean(
        source_reliability,
        algorithmic_consistency,
        quantum_theory_consistency,
        complexity_evidence,
        hardware_evidence,
        contextual_relevance
    );

CONFIDENCE >= 0.90 => HIGH;
CONFIDENCE >= 0.70 AND < 0.90 => MODERATE;
CONFIDENCE < 0.70 => REVIEW;

# ---------- AI CONSUMPTION ----------
AI_CONSUMPTION {
    primary_entity: QuantumAlgorithm;
    ontology: QuantumAlgorithmOntology;
    parse_entities: true;
    parse_relationships: true;
    preserve_relationship_direction: true;
    resolve_semantic_equivalence: true;
    execute_reasoning_rules: true;
    apply_confidence_weighting: true;
    preserve_provenance: true;
}

# ---------- UPDATE MODEL ----------
UPDATE_MODEL {
    new_algorithm:
        validate_problem
        -> identify_encoding
        -> identify_quantum_subroutines
        -> identify_measurements
        -> identify_classical_processing
        -> estimate_resources
        -> integrate;

    new_complexity_evidence:
        identify_model_of_computation
        -> identify_gate_or_query_cost
        -> identify_precision
        -> compare_classical_baseline
        -> integrate;

    new_hardware_evidence:
        identify_target_processor
        -> compile_circuit
        -> estimate_noise_and_depth
        -> update_feasibility
        -> integrate;

    ontology_revision:
        update_algorithm_relationships
        -> update_resource_estimates
        -> update_baseline_comparison
        -> recompute_confidence
        -> regenerate_flow_hash;

    conflict:
        preserve_provenance
        -> compare_theoretical_and_experimental_evidence
        -> adjust_confidence
        -> flag_review;
}

# ---------- FLOW HASH ----------
FLOW_HASH_INPUT :=
    DOMAIN
    + SUBDOMAIN
    + ONTOLOGY
    + AlgorithmEntity
    + AlgorithmPrimitive
    + AlgorithmClass
    + ResourceEntity
    + QuantumAlgorithmComplexity
    + QuantumAdvantage
    + ClassicalBaseline
    + RELATIONSHIPS
    + SEMANTIC_REASONING
    + SEMANTIC_EQUIVALENCE
    + UPDATE_MODEL;

FLOW_HASH :=
    HASH(FLOW_HASH_INPUT);

# ---------- TERMINAL ----------
QuantumAlgorithmOntology
    -> DefineComputationalProblem
    -> EncodeProblemIntoQuantumRepresentation
    -> PrepareRequiredQuantumState
    -> ExecuteQuantumSubroutines
    -> ManipulateAmplitudesAndPhases
    -> MeasureQuantumSystem
    -> AggregateStatisticalOutcomes
    -> PerformClassicalPostprocessing
    -> VerifyResult
    -> EstimateQuantumResources
    -> CompareCompetitiveClassicalBaseline
    -> EvaluatePracticalHardwareFeasibility
    -> MaintainConsistentQuantumAlgorithmKnowledge;

END FLOW