Designing Oracles for Grover Algorithm Notes | EduRev

 Page 1


Designing Oracles 
for Grover Algorithm
Page 2


Designing Oracles 
for Grover Algorithm
Homework
1. You have time until December 3 to return me this homework. 
2. Please use PPT, Word or some word processor. You may send also PDF. The simulation should be done in 
Matlab. Matlab code and all results should be submitted with comments and explanations.
3. The homework is to simulate Grover algorithm on some small oracle of your design.
4. The absolute minimum is to solve the map coloring problem (planar graph coloring) which I discussed in the 
class. You have to show all stages of your design and explanations of design procedures. For doing this part 
of homework you obtain 10 points.
5. If you will add a part of oracle to calculate that the cost of coloring is below certain value T, you will obtain 
another 10 points. See some hints in next slides.
6. If you design an oracle for some other NP-hard or NP-complete problem, different than the graph coloring 
problem, and simulate it successfully, you will obtain a total of 20 points. This cannot be a satisfiability 
problem and the problem should have some practical meaning and not be some arbitrary Boolean function 
as an oracle.
7. Quality of presentation of results, explanation, figures and use of English will be also taken into account 
while grading.
Page 3


Designing Oracles 
for Grover Algorithm
Homework
1. You have time until December 3 to return me this homework. 
2. Please use PPT, Word or some word processor. You may send also PDF. The simulation should be done in 
Matlab. Matlab code and all results should be submitted with comments and explanations.
3. The homework is to simulate Grover algorithm on some small oracle of your design.
4. The absolute minimum is to solve the map coloring problem (planar graph coloring) which I discussed in the 
class. You have to show all stages of your design and explanations of design procedures. For doing this part 
of homework you obtain 10 points.
5. If you will add a part of oracle to calculate that the cost of coloring is below certain value T, you will obtain 
another 10 points. See some hints in next slides.
6. If you design an oracle for some other NP-hard or NP-complete problem, different than the graph coloring 
problem, and simulate it successfully, you will obtain a total of 20 points. This cannot be a satisfiability 
problem and the problem should have some practical meaning and not be some arbitrary Boolean function 
as an oracle.
7. Quality of presentation of results, explanation, figures and use of English will be also taken into account 
while grading.
Examples of Problems for Oracles
• Satisfiability oracles: These oracles are based on creating the single-
output satisfiability formula. The formula can use various gate types 
and structures, depending on the problem.
• Constraint satisfaction oracles: These type of oracles are for constraint 
satisfaction problems such as graph coloring, image matching or 
cryptographic puzzles. These oracles use both logical, arithmetical and 
relational blocks and have often the decision oracle and the 
optimization oracle as their components. The decision oracle is the 
global AND of several partial decision sub-oracles.
• Path problems: These are problems to find certain path in a graph, for 
introduce Euler path or Hamiltonian path. Many games and puzzles 
such as “Man, wolf, Goat and Cabbage” belong to this category. The 
oracles includes decision sub-oracles for each move(edge) in the graph 
of the problem(game)
Page 4


Designing Oracles 
for Grover Algorithm
Homework
1. You have time until December 3 to return me this homework. 
2. Please use PPT, Word or some word processor. You may send also PDF. The simulation should be done in 
Matlab. Matlab code and all results should be submitted with comments and explanations.
3. The homework is to simulate Grover algorithm on some small oracle of your design.
4. The absolute minimum is to solve the map coloring problem (planar graph coloring) which I discussed in the 
class. You have to show all stages of your design and explanations of design procedures. For doing this part 
of homework you obtain 10 points.
5. If you will add a part of oracle to calculate that the cost of coloring is below certain value T, you will obtain 
another 10 points. See some hints in next slides.
6. If you design an oracle for some other NP-hard or NP-complete problem, different than the graph coloring 
problem, and simulate it successfully, you will obtain a total of 20 points. This cannot be a satisfiability 
problem and the problem should have some practical meaning and not be some arbitrary Boolean function 
as an oracle.
7. Quality of presentation of results, explanation, figures and use of English will be also taken into account 
while grading.
Examples of Problems for Oracles
• Satisfiability oracles: These oracles are based on creating the single-
output satisfiability formula. The formula can use various gate types 
and structures, depending on the problem.
• Constraint satisfaction oracles: These type of oracles are for constraint 
satisfaction problems such as graph coloring, image matching or 
cryptographic puzzles. These oracles use both logical, arithmetical and 
relational blocks and have often the decision oracle and the 
optimization oracle as their components. The decision oracle is the 
global AND of several partial decision sub-oracles.
• Path problems: These are problems to find certain path in a graph, for 
introduce Euler path or Hamiltonian path. Many games and puzzles 
such as “Man, wolf, Goat and Cabbage” belong to this category. The 
oracles includes decision sub-oracles for each move(edge) in the graph 
of the problem(game)
• Problems related to spectral transforms:
• The mapping problems, including their special 
class, the subset selection problems.
Page 5


Designing Oracles 
for Grover Algorithm
Homework
1. You have time until December 3 to return me this homework. 
2. Please use PPT, Word or some word processor. You may send also PDF. The simulation should be done in 
Matlab. Matlab code and all results should be submitted with comments and explanations.
3. The homework is to simulate Grover algorithm on some small oracle of your design.
4. The absolute minimum is to solve the map coloring problem (planar graph coloring) which I discussed in the 
class. You have to show all stages of your design and explanations of design procedures. For doing this part 
of homework you obtain 10 points.
5. If you will add a part of oracle to calculate that the cost of coloring is below certain value T, you will obtain 
another 10 points. See some hints in next slides.
6. If you design an oracle for some other NP-hard or NP-complete problem, different than the graph coloring 
problem, and simulate it successfully, you will obtain a total of 20 points. This cannot be a satisfiability 
problem and the problem should have some practical meaning and not be some arbitrary Boolean function 
as an oracle.
7. Quality of presentation of results, explanation, figures and use of English will be also taken into account 
while grading.
Examples of Problems for Oracles
• Satisfiability oracles: These oracles are based on creating the single-
output satisfiability formula. The formula can use various gate types 
and structures, depending on the problem.
• Constraint satisfaction oracles: These type of oracles are for constraint 
satisfaction problems such as graph coloring, image matching or 
cryptographic puzzles. These oracles use both logical, arithmetical and 
relational blocks and have often the decision oracle and the 
optimization oracle as their components. The decision oracle is the 
global AND of several partial decision sub-oracles.
• Path problems: These are problems to find certain path in a graph, for 
introduce Euler path or Hamiltonian path. Many games and puzzles 
such as “Man, wolf, Goat and Cabbage” belong to this category. The 
oracles includes decision sub-oracles for each move(edge) in the graph 
of the problem(game)
• Problems related to spectral transforms:
• The mapping problems, including their special 
class, the subset selection problems.
The Satifiability oracles includes the 
following:
• POS satisfiability.
• Solving unite covering problem by Petrich Function.
• Solving binate covering problem
• Solving various multi-level SAT formulas, especially the 
generalized SAT of the form 
• Solving even-odd covering problem for ESOP , PPRM, 
FPRM and similar minimization problems
• Solving AND-OR DAG from robotics and Artificial 
intelligence.