Quantum vulnerability analysis for patch prioritization
Given a network's vulnerabilities and how their connectivity creates kill-chains — paths to security compromise — decide which vulnerabilities to prioritize for patching, so that those paths are removed.
Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.
Given a network's vulnerabilities and how their connectivity creates kill-chains — paths to security compromise — decide which vulnerabilities to prioritize for patching, so that those paths are removed. Carney introduces vulnerability graphs, related to attack graphs, providing background theory and a method for solving significant cybersecurity problems with quantum computing. As a worked example, the paper prioritizes patches by expressing the connectivity of various vulnerabilities on a network as a QUBO and solving it with quantum annealing. The paper proves that the resulting solution removes all kill-chains — paths to security compromise — on the network. It reports that the quantum computer's solve time is almost constant, compared with an exponential increase in classical solve time, for vulnerability graphs of the density expected in the real world. The author presents this as a novel example of advantageous quantum vulnerability analysis.
Circuit & simulation
problem
encodetransform
algorithm
transformmeasure
readout
measure
What this takes and returns
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
How it works
Carney introduces vulnerability graphs, related to attack graphs, providing background theory and a method for solving significant cybersecurity problems with quantum computing. As a worked example, the paper prioritizes patches by expressing the connectivity of various vulnerabilities on a network as a QUBO and solving it with quantum annealing. The paper proves that the resulting solution removes all kill-chains — paths to security compromise — on the network. It reports that the quantum computer's solve time is almost constant, compared with an exponential increase in classical solve time, for vulnerability graphs of the density expected in the real world. The author presents this as a novel example of advantageous quantum vulnerability analysis. The Classiq library carries this subject under applications · cybersecurity. Reported cost: No proven asymptotic bound. The paper reports, as an experimental finding for vulnerability graphs of the density expected in the real world, that the quantum computer's solve time is almost constant while the classical solve time increases exponentially; the abstract gives no formula, no growth rate, and no qubit, gate, or annealing-time count for either quantity..
Implementation
Unsupported
quantum-vulnerability-analysis.txt
ALGORITHM: Quantum vulnerability analysis for patch prioritization
PROBLEM: Given a network's vulnerabilities and how their connectivity creates kill-chains — paths to security compromise — decide which vulnerabilities to prioritize for patching, so that those paths are removed.
IDEA: Carney introduces vulnerability graphs, related to attack graphs, providing background theory and a method for solving significant cybersecurity problems with quantum computing. As a worked example, the paper prioritizes patches by expressing the connectivity of various vulnerabilities on a network as a QUBO and solving it with quantum annealing. The paper proves that the resulting solution removes all kill-chains — paths to security compromise — on the network. It reports that the quantum computer's solve time is almost constant, compared with an exponential increase in classical solve time, for vulnerability graphs of the density expected in the real world. The author presents this as a novel example of advantageous quantum vulnerability analysis.
REPORTED COST: No proven asymptotic bound. The paper reports, as an experimental finding for vulnerability graphs of the density expected in the real world, that the quantum computer's solve time is almost constant while the classical solve time increases exponentially; the abstract gives no formula, no growth rate, and no qubit, gate, or annealing-time count for either quantity.
BASIS: The abstract of arXiv:2211.13740 states no big-O expression or resource count. Its cost claim is "The results demonstrate that the quantum computer's solve time is almost constant compared to the exponential increase in classical solve time for vulnerability graphs of expected real world density." That is reported as a finding, not derived as a formula: no growth rate, no constant, and no qubit, gate, or annealing-time count accompanies it anywhere in the abstract. The same abstract separately states, "Such a solution is then proved to remove all kill-chains (paths to security compromise) on a network." That is a correctness claim about coverage, not a cost bound, and is not treated as a complexity figure here. The Classiq index entry this record covers, applications/cybersecurity/patching_management, gives a directory path and a file list and states no bound of its own. Those are the only sources read for this field, and the complexity field above is left as a qualitative finding rather than filled with a numeric bound written from memory.
DEMONSTRATED BY: the Classiq library entry applications/cybersecurity/patching_management
PRIMARY SOURCE: Mark Carney (2022), Cutting Medusa's Path -- Tackling Kill-Chains with Quantum Computing — https://arxiv.org/abs/2211.13740
This is a literature reference record, not an executable circuit.
A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Quantum vs classical
Classical baseline
Compare Optimization · Ising encoding with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Declared gaps
Nobody has reviewed this record for gaps yet.
Literature & references
Cutting Medusa's Path -- Tackling Kill-Chains with Quantum Computing2022 · Mark Carney
Primary source: it introduces vulnerability graphs, related to attack graphs, as the background for a QUBO-and-quantum-annealing method that prioritizes patches, proves that the resulting solution removes all kill-chains on a network, and reports that the quantum computer's solve time is almost constant against exponentially increasing classical solve time for vulnerability graphs of real-world density. Consult it for the proof, the formal definition of a kill-chain, and how a vulnerability graph is built from a network — none of which the abstract states.