Algorithms · Optimization · Ising encoding
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.
Attested & literatureUpdated
- Record typeLiterature reference
- Reference implementationpatching_management
- Reported costNo 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.
- Papers1
This record, used inside a worked example
This page says as a QUBO and solving it with quantum annealing
— here is a concrete, runnable instance of it.
QAOA, p=1, MaxCut on a 4-cycle
4 qubits on a 4-cycle (edges 0-1, 1-2, 2-3, 3-0), one QAOA layer with gamma=pi/8, beta=3*pi/8.
Where it ends up
- 010127%
- 101027%
- 00118%
- 01108%
- 12 more outcomes31%
0101 and 1010 are the two optimal cuts of a 4-cycle (alternating around the ring); at these angles measuring the register returns one of them clearly more often than any other cut.
Open that example in StudioGiven 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.
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 →
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..
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 →
- Record type
- Literature reference
- Reference implementation
- patching_management
- 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.
- Complexity 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 demonstration this record covers states no complexity 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.
- Circuit
- Not supplied
This record is not a concrete 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.
Nobody has reviewed this record for gaps yet.
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 demonstration this record covers states no complexity 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.
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.
Related entries
- QUBO operator mapping
Operators
- Ising cost Hamiltonian
Operators
- Ising formulations of NP-complete and NP-hard problems
Algorithms
- Quantum simulated annealing
Algorithms
References
- Cutting Medusa's Path -- Tackling Kill-Chains with Quantum Computing
Mark Carney · 2022
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.