Let's say we want to get a contract. A customer describes what he wants and asks us for when we provide them a completed product.
We are going to use Scrum. How do we calculate the amount of time we need to complete the work?
Scrum isn't used to tell you when something will be delivered. That's not its purpose.
Scrum is used as a framework to develop software transparently that will provide immediate value to its users and customers. It mandates a self-organized, cross-functional team that decides what it works on and when.
This is at cross-purposes with your requirement to deliver pre-specified software by a specific date.
It does not sound like scrum will be the best process to use for your contract; as it is not meant develop software to deliver a complete system by a specific date.
I would recommend a waterfall-esque approach, as it is well suited when the date is the highest priority over all else. You probably still won't deliver everything the client wants; but if the date is the most important thing, you will at least be able to pre-plan towards that.
There are two parts to this answer. The first is how you estimate and the second is if the premise of your question is inherently problematic.
First, the estimation. Generally speaking, there are two broad types of estimation: relative and absolute. Absolute is what we think of in traditional project management. You take a list of tasks and guess at how long they will take based on past experience. Of course, the problem with this is that most knowledge work is very different from task to task making absolute estimation an educated guess at best and a shot in the dark at worst. The fact that you say there are a lot of research tasks means it's probably closer to the shot in the dark.
The second is relative estimation. This is no more accurate than absolute. It is basically using statistical distribution to get "close enough". The potential benefit of relative estimation is that it makes the fuzziness of the estimate obvious and clear.
This desire for a clear answer in estimates matched with the near-impossibility of providing it has gone on as long as there is knowledge work, it's why most people pad their estimates, and it's why projects almost never finish on time. Pragmatically, I can only say that if the only way to win the contract is to give them a date, then give them a date. It'll be wrong, just like every other project. Ideally though, you have a customer who values transparency and prefers to talk in rough forecasts, not absolutes.
Why Use Scrum?
So, the second half of this is basically, why would you use Scrum for a fixed date, fixed scope project? The entire point of Scrum is that you learn what you need as you go. Each sprint has the potential to be a small pivot or a complete re-imagining. Scrum, as a framework, was designed for those types of projects. You will pay a lot of overhead for no value if you plan to create a plan and then simply follow it to completion.
Now, that said, if I were running a software company, I'd use Scrum, but I'd probably only take on contracts where I was able to get the customer into an effective conversation about why they want a Scrum company. That's a choice for your company though.
To use Scrum to good effect you would want the customer to understand that the product is a collaboration to which they will contribute through continuous delivery, review and feedback and product ownership. That being so, a given target date perhaps becomes less important than achieving a sustainable pace and ongoing customer satisfaction.
Once you have an estimated backlog the team can extrapolate a completion date based on expected velocity. Since the date of delivery is always the end of a sprint, the estimates just need to be accurate enough to understand how many sprints are required.
I would like to share a few comments to add to the discussion.
First, a fixed contract means that the client is buying a defined set of working hours for a set price. You will typically present a work plan to the client which will include work packages. The Work Package 1 (WP1) will start on a "Start date of WP1" and will end on WP1 + y w (where y is the number of work weeks that it will take for WP1 to complete). Your time plan will include real dates but these will be indicative, as the people are people, things are not written in stone, and dates and plans and scopes change. I like how nvogel previously explained the meaning of "fixed scope".
Secondly, on Agile cost estimation, what is important is the past experience and how this is documented to aid with the estimation of future projects. An estimation model is no more a necessary component of the process, than is an Expert on the team to help when Expert judgment is needed.
During the requirements analysis stage, you will need to turn the project's requirements into user stories, the stories into tasks and, based on analogy, to estimate them.
We estimate features by analogy given our experience gained from similar projects.
Expert judgment is valuable, when there is no previous experience on a task. Therefore, you need to count on the expertise of an Expert to estimate new features.
Estimating by analogy and Expert judgment will lower your risk.
Some last things I would like to mention:
Firstly it is worth noting that the Scrum framework is designed to use iterative development and feedback to build a better product. You are unlikely to get all of the benefits of Scrum when using it on a fixed-price, fixed-scope project.
As for estimating, there is nothing to stop you using the same method you would use on a traditional project. For example, you could break the work down and then prepare a time-based estimate on it. If you do this before work starts then your estimate will come with all the risks usually associated with long-range estimating.
If you have an established Scrum team you could try and use their velocity to estimate the project delivery. This will at least be using empirical data to produce the estimate, but is it still unlikely to be accurate due to discovery, technical uncertainty, requirements creep, etc.
At this point you may ask the question: is it worth using Scrum?
I think you can still get some benefits from Scrum even on a fixed-price, fixed-scope project. These include: