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.Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!